Binary Tree Traversal (DFS)

This topic serves as an excellent introduction to graph search and divide and conquer. Most (80%) of the BT questions can be solved with D&C. How can you apply the same problem to the left subtree and right subtree?

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 List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorderTraverse(root, result);
    return result;
}

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

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;
}

Iteratively

This is like a regular DFS (w/ opposite ordering). Pretty easy to understand.

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null)
        return result;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode visit = stack.pop();
        result.add(visit.val);
        if (visit.right != null) {
            stack.push(visit.right);
        }
        if (visit.left != null) {
            stack.push(visit.left);
        }
    }

    return result;
}

Inorder Traversal (LC.94)

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

Traverse

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

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

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;
}

Iteratively

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

    Stack<TreeNode> stack = new Stack<>();
    TreeNode visit = root;

    while(visit != null || !stack.isEmpty()) {
        if (visit != null) {
            stack.push(visit);
            visit = visit.left;
        } else {
            visit = stack.pop();
            result.add(visit.val);
            visit = visit.right;
        }
    }

    return result;
}

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);
}

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;
}

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