Tree Traversal

The function is handed a log book from the parameter. Now it needs to travel down this tree and log its visits in a top-down (root to leaf) fashion.

Without using recursion or corecursion specifically, one may traverse a tree by starting at the root node, placing its child nodes in a data structure, then iterating by removing node after node from the data structure while placing each removed node's children back into that data structure.[b] If the data structure is a stack (LIFO), this yields depth-first traversal, and if the data structure is a queue (FIFO), this yields breadth-first traversal. -- Wikipedia

Preorder Traversal (LC.144)

Given a binary tree, return the preorder traversal of its nodes' values.

Analysis

Traverse - traverse the entire tree and add nodes in a certain order. preorder will add root.val in the beginning, inorder will add root.val in the middle, and postorder will add root.val in the end.

D&C - the boss breaks down his task into the same subproblems and assign his employees to do it then report to the boss when they are done. *One major difference b/w traverse and D&C is that D&C must have a return value (the report to the boss).

Iteratively - use an explicit stack and be careful with the ordering. Iterative DFS has the opposite ordering as the recursive DFS.

Traverse

public ArrayList<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> visitLog = new ArrayList<>();
    preOrderHelper(root, visitLog);
    return visitLog;
}

private void preOrderHelper(TreeNode root, ArrayList<Integer> visitLog) {
    // base case
    if (root == null) {
        return;
    }
    // log
    visitLog.add(root.val);
    // visit
    preOrderHelper(root.left, visitLog);
    preOrderHelper(root.right, visitLog);
}

func preorderTraversal(root *TreeNode) []int {
    
    log := []int{}
    
    if root == nil {
        return log
    }
    
    var preorderHelper func(node *TreeNode)
    
    preorderHelper = func(node *TreeNode) {
        // base case 
        if node == nil {
            return
        }

        // preorder traversal 
        log = append(log, node.Val)
        preorderHelper(node.Left)
        preorderHelper(node.Right)
    }
    
    preorderHelper(root)
    
    return log
}

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        log = []
        self.preorderHelper(root, log)
        return log
    
    def preorderHelper(self, root: TreeNode, log: List[int]) -> None:
        if root is None:
            return 
        log.append(root.val)
        self.preorderHelper(root.left, log)
        self.preorderHelper(root.right, log)

D&C

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();

    // base case
    if (root == null) {
        return result;
    }

    // divide
    List<Integer> leftSubtree = preorderTraversal(root.left);
    List<Integer> rightSubtree = preorderTraversal(root.right);

    // conquer
    result.add(root.val);
    result.addAll(leftSubtree);
    result.addAll(rightSubtree);

    return result;
}

def preorderTraversal(self, root: TreeNode) -> List[int]:

    # base 
    if root is None:
        return []

    
    # divide 
    
    left_tree = self.preorderTraversal(root.left)
    right_tree = self.preorderTraversal(root.right)
    
    
    # merge 
    return [root.val] + left_tree + right_tree

Iteratively

Dump children nodes to a data structure. This is like a regular DFS (w/ opposite ordering). Pretty easy to understand.

public ArrayList<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> visitLog = new ArrayList<>();
    if (root == null) {
        return visitLog;
    }
    // init stack
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    // preorder search
    while (!stack.isEmpty()) {
        TreeNode current = stack.pop();
        visitLog.add(current.val);
        if (current.right != null) {
            stack.push(current.right);
        }
        if (current.left != null) {
            stack.push(current.left);
        }
    }
    return visitLog;
}

def preorderTraversal(self, root: TreeNode) -> List[int]:
    
    if root is None:
        return []
    
    # iterative 
    
    stack: List[TreeNode] = []
    log: List[int] = []
    
    stack.append(root)
    
    while len(stack) > 0:
        cur = stack.pop()
        log.append(cur.val)
        if cur.right is not None:
            stack.append(cur.right)
        if cur.left is not None:
            stack.append(cur.left)
    
    return log 

N-ary Tree Preorder Traversal (LI.1526)

public List<Integer> preorder(UndirectedGraphNode root) {
    
    List<Integer> log = new ArrayList<>();
    
    if (root == null) {
        return log;
    }
    
    // iterative 
    
    Stack<UndirectedGraphNode> stack = new Stack<>();
    
    stack.push(root);
    
    while (!stack.isEmpty()) {
        
        UndirectedGraphNode cur = stack.pop();
        
        log.add(cur.label);
        
        for (int i = cur.neighbors.size() - 1; i >= 0; i--) {
            stack.push(cur.neighbors.get(i));
        }
    }
    
    
    return log;
    
}

Inorder Traversal (LC.94)

Given a binary tree, return the inorder traversal of its nodes' values.

Traverse

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> visitLog = new ArrayList<>();
    inOrderHelper(root, visitLog);
    return visitLog;
}

private void inOrderHelper(TreeNode root, ArrayList<Integer> visitLog) {
    // base case
    if (root == null) {
        return;
    }
    // visit left
    inOrderHelper(root.left, visitLog);
    // log
    visitLog.add(root.val);
    // visit right
    inOrderHelper(root.right, visitLog);
}

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        log = []
        self.inorderHelper(root, log)
        return log
    
    def inorderHelper(self, root: TreeNode, log: List[int]) -> None:
        if root is None:
            return 
        self.inorderHelper(root.left, log)
        log.append(root.val)
        self.inorderHelper(root.right, log)

D&C

Trace this one. It makes sense to go down all the way to the left, print and backtrack, print then go right, then backtrack.

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();

    // base case
    if (root == null) {
        return result;
    }

    // divide
    List<Integer> leftSubtree = inorderTraversal(root.left);
    List<Integer> rightSubtree = inorderTraversal(root.right);

    // conquer
    result.addAll(leftSubtree);
    result.add(root.val);
    result.addAll(rightSubtree);

    return result;
}

  def inorderTraversal(self, root: TreeNode) -> List[int]:
      
      # base 
      if root is None:
          return []
      
      # divide 
      left_tree = self.inorderTraversal(root.left)
      right_tree = self.inorderTraversal(root.right)
      
      # merge 
      return left_tree + [root.val] + right_tree 

Iteratively

The else statement kinda works as an iterative backtracking. We want to stop the search when the current pointer is at bottom right of the binary tree and nothing to backtrack to.

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> visitLog = new ArrayList<>();
    if (root == null) { return visitLog; }
    // init stack
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    // inorder search
    while (!stack.isEmpty() || current != null) {
        // left child first
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else {
            // log inorder
            current = stack.pop();
            visitLog.add(current.val);
            // right at last
            current = current.right;
        }
    }
    return visitLog;
}

It can be hard to implement the iterative version of in-order traversal after pre-order traversal. There are 2 distinctions to help clarifying the approach.

1. When to backtrack?

   1. Should be coupled with stack frame being removed

2. Where does the last iteration stop?

   1. Same place with each subtree (the traversal is recursive in nature)

Going through the tree will help visualize the algorithmic movement. But going through a base case will help implement the stop condition correctly.

class Solution:
    
    # dump then pop 
    
    # vs keep dumping then pop 
    
    
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        
        if root is None:
            return []
        
        
        cur = root
        stack = deque()
        log = []
        
        # where does this while loop stop? 
        
        # most right null leaf 
        
        while len(stack) > 0 or cur is not None:
            
            # keep dumping 
            if cur is not None:
                stack.append(cur)
                cur = cur.left  
            else:
                # pop if cur is None
                if len(stack) > 0:
                    cur = stack.pop() # backtracking 
                log.append(cur.val) 
                cur = cur.right
        
        return log

Postorder Traversal (LC.145)

Given a binary tree, return the postorder traversal of its nodes' values.

Traverse

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorderTraverse(root, result);
    return result;
}

private void postorderTraverse(TreeNode root, List<Integer> result) {
    // base case
    if (root == null)
        return;
    postorderTraverse(root.left, result);
    postorderTraverse(root.right, result);
    result.add(root.val);
}

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        log = []
        self.postorderHelper(root, log)
        return log
    
    def postorderHelper(self, root: TreeNode, log: List[int]) -> None:
        if root is None:
            return
        self.postorderHelper(root.left, log)
        self.postorderHelper(root.right, log)
        log.append(root.val)

D&C

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();

    // base case
    if (root == null) {
        return result;
    }

    // divide
    List<Integer> leftSubtree = postorderTraversal(root.left);
    List<Integer> rightSubtree = postorderTraversal(root.right);

    // conquer
    result.addAll(leftSubtree);
    result.addAll(rightSubtree);
    result.add(root.val);

    return result;
}

  def postorderTraversal(self, root: TreeNode) -> List[int]:
      
      # base 
      if root is None:
          return []
      
      # divide 
      left_tree = self.postorderTraversal(root.left)
      right_tree = self.postorderTraversal(root.right)
      
      # merge 
      return left_tree + right_tree + [root.val] 

Iteratively

the key is to understand the use of lastVisit and peek

• peek is for going right first before root

• what about lastVisit? make sure you don't step down on the right path again

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null)
        return result;

    Stack<TreeNode> stack = new Stack<>();
    TreeNode visit = root, lastVisit = null, peek = null;

    while (visit != null || !stack.isEmpty()) {
        if (visit != null) {
            stack.push(visit);
            visit = visit.left;
        } else {
            peek = stack.peek();

            if (peek.right != null && lastVisit != peek.right) {
                visit = peek.right;
            } else {
                result.add(peek.val);
                lastVisit = stack.pop();
            }
        }
    }

    return result;
}

Time & Space Complexity

duh we need to visit all the nodes so time will be O(V). The stack space is proportional to the height of the tree. Note: the height of tree is not necessarily logn, the worst case can be n, a linear tree. So we have O(h) where a balanced tree can be O(logn) and a linear tree can be O(n).

References

Wikipedia Tree Traversal

ʕ； •`ᴥ•´ʔ