13.4 Preorder, Inorder, and Postorder Traversals

Preorder traversal, inorder traversal, and postorder traversal are three ways to traverse a binary tree using Depth-First Search (DFS). They differ only in the order of node visits, while the rest remains the same. Consider the following binary tree:

    1
   / \
  2   3
 / \   \
4   5   6

In preorder traversal, the parent node is visited first, followed by the left node and then the right node. The traversal order is [1 2 4 5 3 6].

C++

void preorder(TreeNode* root) {
    visit(root);
    preorder(root->left);
    preorder(root->right);
}

Python

def preorder(root: TreeNode):
    visit(root)
    preorder(root.left)
    preorder(root.right)

In inorder traversal, the left node is visited first, followed by the parent node and then the right node. The traversal order is [4 2 5 1 3 6].

C++

void inorder(TreeNode* root) {
    inorder(root->left);
    visit(root);
    inorder(root->right);
}

Python

def inorder(root: TreeNode):
    inorder(root.left)
    visit(root)
    inorder(root.right)

In postorder traversal, the left node is visited first, followed by the right node and then the parent node. The traversal order is [4 5 2 6 3 1].

C++

void postorder(TreeNode* root) {
    postorder(root->left);
    postorder(root->right);
    visit(root);
}

Python

def postorder(root: TreeNode):
    postorder(root.left)
    postorder(root.right)
    visit(root)

105. Construct Binary Tree from Preorder and Inorder Traversal

Problem Description

Given the preorder and inorder traversal results of a binary tree, reconstruct the tree. It is guaranteed that there are no duplicate values in the tree nodes.

Input and Output Example

Input consists of two 1D arrays representing the preorder and inorder traversal results of the tree. Output is the reconstructed binary tree.

Input: preorder = [4,9,20,15,7], inorder = [9,4,15,20,7]
Output:
    4
   / \
  9  20
     / \
    15  7

Solution Explanation

Using the provided example, the first node in the preorder traversal is 4, indicating that 4 is the root node. In the inorder traversal, locating 4 provides the following insights:

• The left subarray in the inorder traversal corresponds to the left subtree. It contains 1 node (9), which maps to the next 1 element in the preorder traversal after 4.
• The right subarray in the inorder traversal corresponds to the right subtree. It contains 3 nodes (15, 20, 7), which map to the last 3 elements in the preorder traversal.

With this information, the left and right subtrees can be recursively reconstructed. To simplify locating values, a hash map can be used to preprocess the inorder traversal results.

C++

// Auxiliary function
TreeNode* reconstruct(unordered_map<int, int>& io_map, vector<int>& po, int l,
                      int r, int mid_po) {
    if (l > r) {
        return nullptr;
    }
    int mid_val = po[mid_po];
    int mid_io = io_map[mid_val];
    int left_len = mid_io - l + 1;
    TreeNode* node = new TreeNode(mid_val);
    node->left = reconstruct(io_map, po, l, mid_io - 1, mid_po + 1);
    node->right = reconstruct(io_map, po, mid_io + 1, r, mid_po + left_len);
    return node;
}
// Main function
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> io_map;
    for (int i = 0; i < inorder.size(); ++i) {
        io_map[inorder[i]] = i;
    }
    return reconstruct(io_map, preorder, 0, preorder.size() - 1, 0);
}

Python

# Auxiliary function
def reconstruct(
    io_map: Dict[int, int], po: List[int], l: int, r: int, mid_po: int
) -> Optional[TreeNode]:
    if l > r:
        return None
    mid_val = po[mid_po]
    mid_io = io_map[mid_val]
    left_len = mid_io - l + 1
    node = TreeNode(mid_val)
    node.left = reconstruct(io_map, po, l, mid_io - 1, mid_po + 1)
    node.right = reconstruct(io_map, po, mid_io + 1, r, mid_po + left_len)
    return node

# Main function
def buildTree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    io_map = {val: i for i, val in enumerate(inorder)}
    return reconstruct(io_map, preorder, 0, len(preorder) - 1, 0)

144. Binary Tree Preorder Traversal

Problem Description

Implement a binary tree preorder traversal without using recursion.

Input and Output Example

Input is a binary tree, and the output is an array representing the preorder traversal of the binary tree.

Input:
    1
     \
      2
     /
    3
Output: [1,2,3]

Solution Explanation

Since recursion inherently uses a stack, we can simulate the preorder traversal using an explicit stack. Note the order of stack operations.

C++

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> po;
    if (root == nullptr) {
        return po;
    }
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        po.push_back(node->val);
        if (node->right) {
            s.push(node->right);  // Push the right child first, then the left child, to ensure the left subtree is traversed first.
        }
        if (node->left) {
            s.push(node->left);
        }
    }
    return po;
}

Python

def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
    po = []
    if root is None:
        return po
    s = [root]
    while len(s) > 0:
        node = s.pop()
        po.append(node.val)
        if node.right is not None:
            s.append(node.right)  # Push the right child first, then the left child, to ensure the left subtree is traversed first.
        if node.left is not None:
            s.append(node.left)
    return po