Tree Traversals: PreOrder, InOrder and PostOrder

By Frank Luo

Leetcode Binary Tree Traversal such problems:

1. Binary Tree Traversal
   94. Binary Tree Inorder Traversal
   144. Binary Tree Preorder Traversal
   145. Binary Tree Postorder Traversal

2. N-ary Tree Traversal
   589. N-ary Tree Preorder Traversal
   590. N-ary Tree Postorder Traversal

Binary Tree

PreOrder

Algorithm Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree) 

Recursive

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    preOrder(root, ans);
    return ans;
}

public void preOrder(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    
    list.add(root.val);
    preOrder(root.left, list);
    preOrder(root.right, list);
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Iteration

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return ans;
    }
    while (root != null || !stack.empty()) {
        while (root != null) {
            stack.push(root);
            ans.add(root.val);
            root = root.left;
        }
        
        root = stack.pop();
        root = root.right;
    }
    
    return ans;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

InOrder

Algorithm Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)

Recursive

public List<Integer> inorderTraversal_rec(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    inOrder(root, ans);
    return ans;
}

public void inOrder(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    if (root.left != null) {
        inOrder(root.left, list);
    }
    list.add(root.val);
    if (root.right != null) {
        inOrder(root.right, list);
    }
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Iteration

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return ans;
    }
    
    while (root != null || !stack.empty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        
        root = stack.pop();
        ans.add(root.val);
        root = root.right;
    }
    
    return ans;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

PostOrder

Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.

Recursive

public List<Integer> postorderTraversal_rec(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    postOrder(root, ans);
    return ans;
}

public void postOrder(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    
    postOrder(root.left, list);
    postOrder(root.right, list);
    list.add(root.val);
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Iteration

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return ans;
    }
    
    TreeNode prev = null;
    while (root != null || !stack.empty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }

        root = stack.pop();
        if (root.right == null || root.right == prev) {
            ans.add(root.val);
            prev = root;
            root = null;
        } else {
            stack.push(root);
            root = root.right;
        }
    }

    return ans;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

N-ary Tree Traversal

PreOrder

Recursive

public List<Integer> preorder(Node root) {
    List<Integer> ans = new ArrayList<>();
    preOrderTraversal(root, ans);
    return ans;
}

public void preOrderTraversal(Node root, List<Integer> list) {
    if (root == null) {
        return;
    }
    list.add(root.val);
    List<Node> children = root.children;
    for (Node child : children) {
        preOrderTraversal(child, list);
    }
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Iteration

public List<Integer> preorder(Node root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        Node node = stack.pop();
        ans.add(node.val);
        List<Node> children = node.children;
        int size = children.size();
        for (int i = size - 1; i >= 0; i--) {
            stack.push(children.get(i));
        }
    }
    
    return ans;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

PostOrder

Recursive

public List<Integer> postorder_rec(Node root) {
    List<Integer> ans = new ArrayList<>();
    postOrderTraversal(root, ans);
    return ans;
}

public void postOrderTraversal(Node root, List<Integer> list) {
    if (root == null) {
        return;
    }
    List<Node> children = root.children;
    for (Node child : children) {
        postOrderTraversal(child, list);
    }
    list.add(root.val);
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Iteration

public List<Integer> postorder(Node root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        Node node = stack.pop();
        ans.add(node.val);
        List<Node> children = node.children;
        int size = children.size();
        for (int i = 0; i < size; i++) {
            stack.push(children.get(i));
        }
    }
    
    Collections.reverse(ans);
    return ans;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗