Can you please suggest how to find and replace just a first left node in a tree. I have implemented method that replaces all nodes:

from dataclasses import dataclass, field
import typing 
from typing import List

@dataclass()
class Node:
  value: str
  children: List[Node] = field(default_factory=lambda: [])

# replaces all nodes
def substitute(source, original, replacement):
  if source == original:
    source.value = replacement.value
    source.children = replacement.children
    return source
  else:
    source.children = [substitute(child, original, replacement) for child in source.children]
    return source 

t1 = Node('r', [Node('r2', [Node('2')]), Node('2')])
substitute(t1, Node('2'), Node('5')) # will substitue all Node('2') -> Node('5')

How to implement method that replaces only first left occurrence (Postorder) of Node('2')?

Node('r', [Node('r2', [Node('2')]), Node('2')]) -> Node('r', [Node('r2', [Node('5')]), Node('2')])

CodePudding user response：

As your substitute function mutates the given tree, there is no real need to also have it return it.

You could instead have it return a boolean that indicates whether a replacement was done or not.

This way you can then write an alternative substitute_first function and detect whether a recursive call returned True, which would be a signal to not do any more replacements, but just return True to the caller, so exiting the recursion tree quickly.

Here is the code:

def substitute_first(source, original, replacement):
  if any(substitute_first(child, original, replacement) for child in source.children):
      return True  # A replacement was made in recursion
  if source == original:
    source.value = replacement.value
    source.children = replacement.children
    return True
  return False