Binary Tree in Action (Construction)

labuladongOriginalAbout 9382 words

This article will resolve

LeetCode	Difficulty
105. Construct Binary Tree from Preorder and Inorder Traversal	🟠
106. Construct Binary Tree from Inorder and Postorder Traversal	🟠
654. Maximum Binary Tree	🟠
889. Construct Binary Tree from Preorder and Postorder Traversal	🟠

Prerequisite Knowledge

Before reading this article, you need to study:

This article is the second part following Essentials of Binary Trees (Guidelines). Let's first recap the main ideas for solving binary tree problems summarized in the previous article:

Note

The thought process for solving binary tree problems can be divided into two categories:

1. Can you obtain the answer by traversing the binary tree once? If so, use a traverse function with external variables to achieve this, which is the "traversal" mindset.

2. Can you define a recursive function to derive the answer to the original problem from the answers to subproblems (subtrees)? If so, write out the definition of this recursive function and make full use of its return value, which is the "problem decomposition" mindset.

Regardless of the mindset used, you need to consider:

What does an individual binary tree node need to do? When (pre/in/post-order position) should it do this? You don't need to worry about other nodes; the recursive function will perform the same operations on all nodes.

The first article Essentials of Binary Trees (Mindset) discussed the "traversal" and "problem decomposition" mindsets. This article covers the construction-type problems of binary trees.

Construction problems of binary trees generally use the "problem decomposition" approach: constructing the entire tree = root node + constructing the left subtree + constructing the right subtree.

Now, let's directly look at a problem.

Constructing Maximum Binary Tree

Let's start with a simple one, this is LeetCode Problem 654 "Maximum Binary Tree", the problem is as follows:

654. Maximum Binary Tree | LeetCode | 🟠

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

Create a root node whose value is the maximum value in nums.
Recursively build the left subtree on the subarray prefix to the left of the maximum value.
Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

Example 1:

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
    - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
        - Empty array, so no child.
        - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
            - Empty array, so no child.
            - Only one element, so child is a node with value 1.
    - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
        - Only one element, so child is a node with value 0.
        - Empty array, so no child.

Example 2:

Input: nums = [3,2,1]
Output: [3,null,2,null,1]

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
All integers in nums are unique.

The problem is from LeetCode 654. Maximum Binary Tree.

java

// function signature as follows
TreeNode constructMaximumBinaryTree(int[] nums);

cpp

// The function signature is as follows
TreeNode* constructMaximumBinaryTree(vector<int>& nums);

python

# The function signature is as follows
def constructMaximumBinaryTree(nums: List[int]) -> TreeNode:

// The function signature is as follows
func constructMaximumBinaryTree(nums []int) *TreeNode

javascript

// function signature as follows
var constructMaximumBinaryTree = function(nums) {};

Each node in a binary tree can be considered the root of a subtree. For the root node, the first thing to do is to construct itself, and then find a way to construct its left and right subtrees.

Therefore, we need to traverse the array to find the maximum value maxVal, then create the root node root with this value. Next, we recursively construct the left subtree from the elements to the left of maxVal and the right subtree from the elements to the right of maxVal.

According to the example given in the problem, the input array is [3,2,1,6,0,5]. For the root node of the entire tree, we are essentially doing this:

java 🟢

TreeNode constructMaximumBinaryTree([3,2,1,6,0,5]) {
    // find the maximum value in the array
    TreeNode root = new TreeNode(6);
    // recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree([3,2,1]);
    root.right = constructMaximumBinaryTree([0,5]);
    return root;
}

// the maximum value in the current nums is the root node, and then
// recursively call the left and right arrays to construct the left and right subtrees
// in more detail, the pseudocode is as follows
TreeNode constructMaximumBinaryTree(int[] nums) {
    if (nums is empty) return null;
    // find the maximum value in the array
    int maxVal = Integer.MIN_VALUE;
    int index = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
            index = i;
        }
    }

    TreeNode root = new TreeNode(maxVal);
    // recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree(nums[0..index-1]);
    root.right = constructMaximumBinaryTree(nums[index+1..nums.length-1]);
    return root;
}

cpp 🤖

TreeNode* constructMaximumBinaryTree([3,2,1,6,0,5]) {
    // find the maximum value in the array
    TreeNode* root = new TreeNode(6);
    // recursively construct the left and right subtrees
    root->left = constructMaximumBinaryTree({3,2,1});
    root->right = constructMaximumBinaryTree({0,5});
    return root;
}

// the current maximum value in nums is the root node, and then
// recursively construct the left and right subtrees based on the index
// more specifically, the pseudocode is as follows
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    if (nums.empty()) return nullptr;

    // find the maximum value in the array
    int maxVal = INT_MIN;
    int index = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
            index = i;
        }
    }

    TreeNode* root = new TreeNode(maxVal);
    // recursively construct the left and right subtrees
    root->left = constructMaximumBinaryTree(nums[0..index-1]);
    root->right = constructMaximumBinaryTree(nums[index+1..nums.size()-1]);
}

python 🤖

def constructMaximumBinaryTree([3,2,1,6,0,5]) -> TreeNode:
    # find the maximum value in the array
    root = TreeNode(6)
    # recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree([3,2,1])
    root.right = constructMaximumBinaryTree([0,5])
    return root

# the current maximum value in nums is the root node, then recursively
# construct the left and right subtrees based on the indices of the subarrays
# in more detail, the pseudocode is as follows
def constructMaximumBinaryTree(nums: List[int]) -> TreeNode:
    if not nums: 
        return None

    # find the maximum value in the array
    maxVal = max(nums)
    index = nums.index(maxVal)

    root = TreeNode(maxVal)
    # recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree(nums[:index])
    root.right = constructMaximumBinaryTree(nums[index+1:])
    return root

go 🤖

func constructMaximumBinaryTree([3,2,1,6,0,5]) *TreeNode {
    // find the maximum value in the array
    root := &TreeNode{Val: 6}
    // recursively construct left and right subtrees
    root.Left = constructMaximumBinaryTree([]int{3,2,1})
    root.Right = constructMaximumBinaryTree([]int{0,5})
    return root
}

// the current maximum value in nums is the root node, and then
// recursively construct left and right subtrees based on the index
// in more detail, the pseudocode is as follows
func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    // find the maximum value in the array
    maxVal := math.MinInt32
    index := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] > maxVal {
            maxVal = nums[i]
            index = i
        }
    }

    root := &TreeNode{Val: maxVal}
    // recursively construct left and right subtrees
    root.Left = constructMaximumBinaryTree(nums[:index])
    root.Right = constructMaximumBinaryTree(nums[index+1:])
    return root
}

javascript 🤖

var constructMaximumBinaryTree = function([3,2,1,6,0,5]) {
    // find the maximum value in the array
    var root = new TreeNode(6);
    // recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree([3,2,1]);
    root.right = constructMaximumBinaryTree([0,5]);
    return root;
}

// the maximum value in the current nums is the root node, then
// recursively construct the left and right subtrees based on the index
// in more detail, it is as follows in pseudocode
var constructMaximumBinaryTree = function(nums) {
    if (nums.length === 0) return null;

    // find the maximum value in the array
    var maxVal = Math.max(...nums);
    var index = nums.indexOf(maxVal);

    var root = new TreeNode(maxVal);
    // recursively construct the left and right subtrees
    root.left = constructMaximumBinaryTree(nums.slice(0, index));
    root.right = constructMaximumBinaryTree(nums.slice(index + 1, nums.length));
    
    return root;
}

The maximum value in the current nums is the root node. Then, recursively call the left and right arrays based on the index to construct the left and right subtrees.

With this idea clear, we can write an auxiliary function build to control the indices of nums:

java 🟢

class Solution {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    // Definition: Construct a tree from nums[lo..hi]
    // that meets the conditions, return the root node
    TreeNode build(int[] nums, int lo, int hi) {
        // base case
        if (lo > hi) {
            return null;
        }

        // Find the maximum value in the array and its corresponding index
        int index = -1, maxVal = Integer.MIN_VALUE;
        for (int i = lo; i <= hi; i++) {
            if (maxVal < nums[i]) {
                index = i;
                maxVal = nums[i];
            }
        }

        // First construct the root node
        TreeNode root = new TreeNode(maxVal);
        // Recursively construct the left and right subtrees
        root.left = build(nums, lo, index - 1);
        root.right = build(nums, index + 1, hi);
        
        return root;
    }
}

cpp 🤖

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, nums.size()-1);
    }

private:
    // Definition: Construct a tree from nums[lo..hi] that
    // meets the conditions and return the root node
    TreeNode* build(vector<int>& nums, int lo, int hi) {
        // base case
        if (lo > hi) {
            return nullptr;
        }

        // Find the maximum value in the array and its corresponding index
        int index = -1, maxVal = INT_MIN;
        for (int i = lo; i <= hi; i++) {
            if (maxVal < nums[i]) {
                index = i;
                maxVal = nums[i];
            }
        }

        // First, construct the root node
        TreeNode* root = new TreeNode(maxVal);
        // Recursively construct the left and right subtrees
        root->left = build(nums, lo, index - 1);
        root->right = build(nums, index + 1, hi);
        
        return root;
    }
};

python 🤖

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        return self.build(nums, 0, len(nums) - 1)

    # Definition: Construct the tree that meets the
    # requirements from nums[lo..hi] and return the root node
    def build(self, nums: List[int], lo: int, hi: int) -> TreeNode:
        # base case
        if lo > hi:
            return None

        # Find the maximum value in the array and its corresponding index
        index = -1
        maxVal = float('-inf')
        for i in range(lo, hi + 1):
            if maxVal < nums[i]:
                index = i
                maxVal = nums[i]

        # First, construct the root node
        root = TreeNode(maxVal)
        # Recursively construct the left and right subtrees
        root.left = self.build(nums, lo, index - 1)
        root.right = self.build(nums, index + 1, hi)
        
        return root

go 🤖

func constructMaximumBinaryTree(nums []int) *TreeNode {
    return build(nums, 0, len(nums) - 1)
}

// Definition: construct a tree with nums[lo..hi]
// that meets the conditions, and return the root node
func build(nums []int, lo, hi int) *TreeNode {
    // base case
    if lo > hi {
        return nil
    }

    // find the maximum value in the array and its corresponding index
    index := -1
    maxVal := -1 << 31
    for i := lo; i <= hi; i++ {
        if maxVal < nums[i] {
            index = i
            maxVal = nums[i]
        }
    }

    // first construct the root node
    root := &TreeNode{Val: maxVal}
    // recursively construct the left and right subtrees
    root.Left = build(nums, lo, index - 1)
    root.Right = build(nums, index + 1, hi)
    
    return root
}

javascript 🤖

var constructMaximumBinaryTree = function(nums) {
    return build(nums, 0, nums.length - 1);
}

// Definition: construct a tree from nums[lo..hi]
// that meets the conditions, and return the root node
function build(nums, lo, hi) {
    // base case
    if (lo > hi) {
        return null;
    }

    // find the maximum value in the array and its corresponding index
    let index = -1, maxVal = Number.MIN_SAFE_INTEGER;
    for (let i = lo; i <= hi; i++) {
        if (maxVal < nums[i]) {
            index = i;
            maxVal = nums[i];
        }
    }

    // first, construct the root node
    let root = new TreeNode(maxVal);
    // recursively construct the left and right subtrees
    root.left = build(nums, lo, index - 1);
    root.right = build(nums, index + 1, hi);
    
    return root;
}

Algorithm Visualization

At this point, this problem is solved. It was quite simple, right? Let's look at two more challenging problems.

Constructing a Binary Tree from Preorder and Inorder Traversal

LeetCode Problem 105, "Construct Binary Tree from Preorder and Inorder Traversal," is a classic question frequently tested in interviews and exams:

105. Construct Binary Tree from Preorder and Inorder Traversal | LeetCode | 🟠

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder consist of unique values.
Each value of inorder also appears in preorder.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.

The problem is from LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal.

java 🟢

// The function signature is as follows
TreeNode buildTree(int[] preorder, int[] inorder);

cpp 🤖

// The function signature is as follows
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder);

python 🤖

# the function signature is as follows
def buildTree(preorder: List[int], inorder: List[int]):

go 🤖

// The function signature is as follows
func buildTree(preorder []int, inorder []int) *TreeNode

javascript 🤖

// The function signature is as follows
var buildTree = function(preorder, inorder) {};

Let's get straight to the point and think about the approach. First, consider what the root node should do.

Similar to the previous problem, we need to determine the value of the root node, create the root node, and then recursively construct the left and right subtrees.

Let's review the characteristics of the preorder and inorder traversal results.

java 🟢

void traverse(TreeNode root) {
    // preorder traversal
    preorder.add(root.val);
    traverse(root.left);
    traverse(root.right);
}

void traverse(TreeNode root) {
    traverse(root.left);
    // inorder traversal
    inorder.add(root.val);
    traverse(root.right);
}

cpp 🤖

void traverse(TreeNode* root) {
    if(root == NULL)
        return;
    // pre-order traversal
    preorder.push_back(root->val);
    traverse(root->left);
    traverse(root->right);
}

void traverse(TreeNode* root) {
    if(root == NULL)
        return;
    traverse(root->left);
    // in-order traversal
    inorder.push_back(root->val);
    traverse(root->right);
}

python 🤖

def traverse(root):
    if not root:
        return
    # pre-order traversal
    preorder.append(root.val)
    traverse(root.left)
    traverse(root.right)

def traverse(root):
    if not root:
        return
    traverse(root.left)
    # in-order traversal
    inorder.append(root.val)
    traverse(root.right)

go 🤖

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // preorder traversal
    preorder = append(preorder, root.Val)
    traverse(root.Left)
    traverse(root.Right)
}

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    // inorder traversal
    inorder = append(inorder, root.Val)
    traverse(root.Right)
}

javascript 🤖

var traverse = function(root) {
    if (root === null) {
        return;
    }
    // preorder traversal
    preorder.push(root.val);
    traverse(root.left);
    traverse(root.right);
}

var traverse = function(root) {
    if (root === null) {
        return;
    }
    traverse(root.left);
    // inorder traversal
    inorder.push(root.val);
    traverse(root.right);
}

In the previous article The Frameworks of Binary Trees, it was discussed how the different traversal orders lead to certain characteristics in the distribution of elements in the preorder and inorder arrays:

Finding the root node is quite simple; the first value preorder[0] in the preorder traversal is the root node's value.

The key question is how to use the root node's value to divide the preorder and inorder arrays into two halves to construct the left and right subtrees of the root node.

In other words, what should be filled in the ? part of the following code:

java 🟢

TreeNode buildTree(int[] preorder, int[] inorder) {
    // According to the function definition, construct the
    // binary tree using preorder and inorder arrays
    return build(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
}

// Definition of the build function:
// If the preorder traversal array is preorder[preStart..preEnd],
// and the inorder traversal array is inorder[inStart..inEnd],
// construct the binary tree and return its root node
TreeNode build(int[] preorder, int preStart, int preEnd, 
            int[] inorder, int inStart, int inEnd) {
    // The value of the root node corresponds to the first element of the preorder array
    int rootVal = preorder[preStart];
    // The index of rootVal in the inorder array
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }

    TreeNode root = new TreeNode(rootVal);
    // Recursively construct the left and right subtrees
    root.left = build(preorder, ?, ?,
                    inorder, ?, ?);

    root.right = build(preorder, ?, ?,
                    inorder, ?, ?);
    return root;
}

cpp 🤖

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    // According to the function definition, construct
    // the binary tree using preorder and inorder
    return build(preorder, 0, preorder.size() - 1,
                inorder, 0, inorder.size() - 1);
}

// Definition of the build function:
// If the preorder traversal array is preorder[preStart..preEnd],
// and the inorder traversal array is inorder[inStart..inEnd],
// build the binary tree and return the root node of the tree
TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                vector<int>& inorder, int inStart, int inEnd) {
    if (preStart > preEnd) {
        return NULL;
    }
    // The value of the root node is the first element of the preorder traversal array
    int rootVal = preorder[preStart];
    int index;
    for (int i = inStart; i<= inEnd; i++) {
        // The index of rootVal in the inorder traversal array
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }
    TreeNode* root = new TreeNode(rootVal);
    int leftSize = index - inStart;
    // Recursively construct the left and right subtrees
    root->left = build(preorder, ?, ?,
                    inorder, ?, ?);

    root->right = build(preorder, ?, ?,
                    inorder, ?, ?);
    return root;
}

python 🤖

def buildTree(preorder, inorder):
    # According to the function definition, use
    # preorder and inorder to construct the binary tree
    return build(preorder, 0, len(preorder) - 1,
                inorder, 0, len(inorder) - 1)

# Definition of build function:
# If the preorder traversal array is preorder[preStart..preEnd],
# and the inorder traversal array is inorder[inStart..inEnd],
# construct the binary tree and return its root node
def build(preorder, preStart, preEnd, 
            inorder, inStart, inEnd):
    # The value of the root node is the first element in the preorder traversal array
    rootVal = preorder[preStart]
    # The index of rootVal in the inorder traversal array
    index = 0
    for i in range(inStart, inEnd + 1):
        if inorder[i] == rootVal:
            index = i
            break

    root = TreeNode(rootVal)
    # Recursively construct the left and right subtrees
    root.left = build(preorder, ?, ?,
                    inorder, ?, ?)

    root.right = build(preorder, ?, ?,
                    inorder, ?, ?)
    return root

go 🤖

func buildTree(preorder []int, inorder []int) *TreeNode {
    // According to the function definition, construct
    // the binary tree using preorder and inorder
    return build(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
}

// Definition of the build function:
// If the preorder traversal array is preorder[preStart..preEnd],
// and the inorder traversal array is inorder[inStart..inEnd],
// construct the binary tree and return its root node
func build(preorder []int, preStart int, preEnd int, 
           inorder []int, inStart int, inEnd int) *TreeNode {
    if preStart > preEnd {
        return nil
    }
    // The value corresponding to the root node is the first element of the preorder array
    rootVal := preorder[preStart]
    // The index of rootVal in the inorder array
    index := 0
    for i := inStart; i <= inEnd; i++ {
        if inorder[i] == rootVal {
            index = i
            break
        }
    }
    root := &TreeNode{Val: rootVal}
    sizeLeftSubtree := index - inStart
    // Recursively construct the left and right subtrees
    root.Left = build(preorder, ?, ?,
                    inorder, ?, ?)
    root.Right = build(preorder, ?, ?,
                    inorder, ?, ?)
    return root
}

javascript 🤖

var buildTree = function(preorder, inorder) {
    // According to the function definition, construct
    // the binary tree using preorder and inorder
    return build(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
}

// Definition of the build function:
// If the preorder traversal array is preorder[preStart..preEnd],
// and the inorder traversal array is inorder[inStart..inEnd],
// construct the binary tree and return the root node of the binary tree
var build = function(preorder, preStart, preEnd, 
                    inorder, inStart, inEnd) {
    // The value corresponding to the root node is the
    // first element of the preorder traversal array
    var rootVal = preorder[preStart];

    // The index of rootVal in the inorder traversal array
    var index = 0;
    for (var i = inStart; i <= inEnd; i++) {
        if (inorder[i] === rootVal) {
            index = i;
            break;
        }
    }

    var root = new TreeNode(rootVal);

    // Recursively construct the left and right subtrees
    root.left = build(preorder, ?, ?,
                    inorder, ?, ?);

    root.right = build(preorder, ?, ?,
                    inorder, ?, ?);

    return root;
}

In the code, the variables rootVal and index refer to the situation illustrated in the image below:

Additionally, some readers have pointed out that using a for loop to determine index is not very efficient and can be further optimized.

Since the problem states that the values of the binary tree nodes are unique, a HashMap can be used to store the mapping of elements to their indices. This allows you to directly find the index corresponding to rootVal using the HashMap:

java 🟢

// store the value-to-index mapping in inorder
HashMap<Integer, Integer> valToIndex = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) {
        valToIndex.put(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1);
}

TreeNode build(int[] preorder, int preStart, int preEnd, 
               int[] inorder, int inStart, int inEnd) {
    int rootVal = preorder[preStart];
    // avoid using a for loop to find rootVal
    int index = valToIndex.get(rootVal);
    // ...
}

cpp 🤖

// store the mapping of values to indices in inorder
unordered_map<int, int> valToIndex;

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    for (int i = 0; i < inorder.size(); i++) {
        valToIndex[inorder[i]] = i;
    }
    return build(preorder, 0, preorder.size() - 1,
                 inorder, 0, inorder.size() - 1);
}

TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                vector<int>& inorder, int inStart, int inEnd) {
    int rootVal = preorder[preStart];
    // avoid using a for loop to find rootVal
    int index = valToIndex[rootVal];
    // ...
}

python 🤖

# store the mapping from values to indices in inorder
val_to_index = {}

def build_tree(preorder, inorder):

    for i in range(len(inorder)):
        val_to_index[inorder[i]] = i

    return build(preorder, 0, len(preorder) - 1,
                 inorder, 0, len(inorder) - 1)

def build(preorder, pre_start, pre_end, 
          inorder, in_start, in_end):
  
    root_val = preorder[pre_start]
    # avoid using for loop to find rootVal
    index = val_to_index[root_val]
    # ...

go 🤖

// store the mapping from values to indices in inorder
valToIndex := make(map[int]int)

func buildTree(preorder []int, inorder []int) *TreeNode {
    for i := 0; i < len(inorder); i++ {
        valToIndex[inorder[i]] = i
    }
    return build(preorder, 0, len(preorder) - 1,
                 inorder, 0, len(inorder) - 1)
}

func build(preorder []int, preStart int, preEnd int,
           inorder []int, inStart int, inEnd int) *TreeNode {
           
    rootVal := preorder[preStart]
    // avoid using a for loop to find rootVal
    index := valToIndex[rootVal]
    // ...
}

javascript 🤖

// store the mapping from values to indices in inorder
var valToIndex = {};

var buildTree = function(preorder, inorder) {
    for (var i = 0; i < inorder.length; i++) {
        valToIndex[inorder[i]] = i;
    }
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1);
};

var build = function(preorder, preStart, preEnd, 
               inorder, inStart, inEnd) {
    var rootVal = preorder[preStart];
    // avoid using a for loop to find rootVal
    var index = valToIndex[rootVal];
    // ...
};

Now let's look at the picture and fill in the blanks. What should be filled in the question marks below:

java 🟢

root.left = build(preorder, ?, ?,
                  inorder, ?, ?);

root.right = build(preorder, ?, ?,
                   inorder, ?, ?);

cpp 🤖

root->left = build(preorder, ?, ?,
                   inorder, ?, ?);

root->right = build(preorder, ?, ?,
                   inorder, ?, ?);

python 🤖

root.left = build(preorder, ?, ?,
                  inorder, ?, ?)

root.right = build(preorder, ?, ?,
                   inorder, ?, ?)

go 🤖

root.Left = build(preorder, ?, ?,
                  inorder, ?, ?)

root.Right = build(preorder, ?, ?,
                   inorder, ?, ?)

javascript 🤖

root.left = build(preorder, ?, ?,
                  inorder, ?, ?);

root.right = build(preorder, ?, ?,
                   inorder, ?, ?);

The starting and ending indices for the inorder arrays corresponding to the left and right subtrees are relatively easy to determine:

java 🟢

root.left = build(preorder, ?, ?,
                  inorder, inStart, index - 1);

root.right = build(preorder, ?, ?,
                   inorder, index + 1, inEnd);

cpp 🤖

root->left = build(preorder, ?, ?,
                   inorder, inStart, index - 1);

root->right = build(preorder, ?, ?,
                   inorder, index + 1, inEnd);

python 🤖

root.left = build(preorder, ?, ?, inorder, inStart, index - 1)

root.right = build(preorder, ?, ?, inorder, index + 1, inEnd)

go 🤖

root.Left = build(preorder, ?, ?, 
                  inorder, inStart, index - 1)

root.Right = build(preorder, ?, ?, 
                   inorder, index + 1, inEnd)

javascript 🤖

root.left = build(preorder, ?, ?, 
                inorder, inStart, index - 1);

root.right = build(preorder, ?, ?, 
                    inorder, index + 1, inEnd);

How about the preorder array? How do we determine the starting and ending indices for the left and right subarrays?

This can be deduced from the number of nodes in the left subtree. Let's assume the number of nodes in the left subtree is leftSize. The index situation in the preorder array is as follows:

By looking at this diagram, you can write out the corresponding indices for the preorder array:

java 🟢

int leftSize = index - inStart;

root.left = build(preorder, preStart + 1, preStart + leftSize,
                  inorder, inStart, index - 1);

root.right = build(preorder, preStart + leftSize + 1, preEnd,
                   inorder, index + 1, inEnd);

cpp 🤖

int leftSize = index - inStart;

root->left = build(preorder, preStart + 1, preStart + leftSize,
                   inorder, inStart, index - 1);

root->right = build(preorder, preStart + leftSize + 1, preEnd,
                    inorder, index + 1, inEnd);

python 🤖

leftSize = index - inStart

root.left = build(preorder, preStart + 1, preStart + leftSize,
                  inorder, inStart, index - 1)

root.right = build(preorder, preStart + leftSize + 1, preEnd,
                   inorder, index + 1, inEnd)

go 🤖

leftSize := index - inStart

root.Left = build(preorder, preStart + 1, preStart + leftSize,
                  inorder, inStart, index - 1)

root.Right = build(preorder, preStart + leftSize + 1, preEnd,
                   inorder, index + 1, inEnd)

javascript 🤖

var leftSize = index - inStart;

root.left = build(preorder, preStart + 1, preStart + leftSize,
                  inorder, inStart, index - 1);

root.right = build(preorder, preStart + leftSize + 1, preEnd,
                   inorder, index + 1, inEnd);

At this point, the entire algorithm approach is complete. We just need to handle the base case to write the solution code:

java 🟢

class Solution {
    // Store the mapping of values to indices in inorder
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1,
                    inorder, 0, inorder.length - 1);
    }

    // Definition of the build function:
    // If the preorder traversal array is preorder[preStart..preEnd],
    // and the inorder traversal array is inorder[inStart..inEnd],
    // construct the binary tree and return its root node
    TreeNode build(int[] preorder, int preStart, int preEnd, 
               int[] inorder, int inStart, int inEnd) {

        if (preStart > preEnd) {
            return null;
        }

        // The value of the root node corresponds to the first element in the preorder array
        int rootVal = preorder[preStart];
        // The index of rootVal in the inorder array
        int index = valToIndex.get(rootVal);

        int leftSize = index - inStart;

        // First, construct the current root node
        TreeNode root = new TreeNode(rootVal);
        // Recursively construct the left and right subtrees
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                        inorder, inStart, index - 1);

        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                        inorder, index + 1, inEnd);
        return root;
    }
}

cpp 🤖

class Solution {
public:
    // store the mapping from value to index in inorder
    unordered_map<int, int> valToIndex;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++) {
            valToIndex[inorder[i]] = i;
        }
        return build(preorder, 0, preorder.size() - 1,
                    inorder, 0, inorder.size() - 1);
    }

    // definition of build function:
    // if the preorder array is preorder[preStart..preEnd],
    // and the inorder array is inorder[inStart..inEnd],
    // construct the binary tree and return its root node
    TreeNode* build(vector<int>& preorder, int preStart, int preEnd, 
                    vector<int>& inorder, int inStart, int inEnd) {

        if (preStart > preEnd) {
            return NULL;
        }

        // the value of the root node is the first element of the preorder array
        int rootVal = preorder[preStart];
        // the index of rootVal in the inorder array
        int index = valToIndex[rootVal];

        int leftSize = index - inStart;

        // first construct the current root node
        TreeNode* root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        root->left = build(preorder, preStart + 1, preStart + leftSize,
                        inorder, inStart, index - 1);

        root->right = build(preorder, preStart + leftSize + 1, preEnd,
                        inorder, index + 1, inEnd);
        return root;
    }
};

python 🤖

class Solution:
    # store the mapping from values in inorder to their indices
    valToIndex = dict()

    def buildTree(self, preorder, inorder):
        for i in range(len(inorder)):
            self.valToIndex[inorder[i]] = i
        return self.build(preorder, 0, len(preorder) - 1,
                          inorder, 0, len(inorder) - 1)

    # definition of the build function:
    # if the preorder traversal array is preorder[preStart..preEnd],
    # and the inorder traversal array is inorder[inStart..inEnd],
    # construct the binary tree and return its root node
    def build(self, preorder, preStart, preEnd,
               inorder, inStart, inEnd):
        if preStart > preEnd:
            return None

        # the root node's value is the first element in the preorder array
        rootVal = preorder[preStart]
        # the index of rootVal in the inorder array
        index = self.valToIndex[rootVal]

        leftSize = index - inStart

        # first construct the current root node
        root = TreeNode(rootVal) 

        # recursively construct the left and right subtrees
        root.left = self.build(preorder, preStart + 1, preStart + leftSize,
                               inorder, inStart, index - 1)

        root.right = self.build(preorder, preStart + leftSize + 1, preEnd,
                                inorder, index + 1, inEnd)

        return root

go 🤖

func buildTree(preorder []int, inorder []int) *TreeNode {
    valToIndex := make(map[int]int)
    for i := 0; i < len(inorder); i++ {
        valToIndex[inorder[i]] = i
    }

    var build func([]int, int, int, []int, int, int) *TreeNode
    build = func(preorder []int, preStart, preEnd int, inorder []int, inStart, inEnd int) *TreeNode {
        if preStart > preEnd {
            return nil
        }

        // the value corresponding to the root node is the first element of the preorder array
        rootVal := preorder[preStart]
        // the index of rootVal in the inorder array
        index := valToIndex[rootVal]
        leftSize := index - inStart

        // first construct the current root node
        root := &TreeNode{Val: rootVal}
        // recursively construct the left and right subtrees
        root.Left = build(preorder, preStart+1, preStart+leftSize, inorder, inStart, index-1)
        root.Right = build(preorder, preStart+leftSize+1, preEnd, inorder, index+1, inEnd)
        return root
    }

    return build(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
}

javascript 🤖

var buildTree = function(preorder, inorder) {
    // store the mapping from value to index in inorder
    var valToIndex = new Map();

    for (let i = 0; i < inorder.length; i++) {
        valToIndex.set(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);

    // definition of build function:
    // if the preorder array is preorder[preStart..preEnd],
    // and the inorder array is inorder[inStart..inEnd],
    // construct the binary tree and return its root node
    function build(preorder, preStart, preEnd, 
               inorder, inStart, inEnd) {

        if (preStart > preEnd) {
            return null;
        }

        // the value of the root node is the first element of the preorder array
        var rootVal = preorder[preStart];
        // the index of rootVal in the inorder array
        var index = valToIndex.get(rootVal);

        var leftSize = index - inStart;

        // first construct the current root node
        var root = new TreeNode(rootVal);
        // recursively build the left and right subtrees
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                        inorder, inStart, index - 1);

        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                        inorder, index + 1, inEnd);
        return root;
    }
};

Our main function only needs to call the buildTree function. At first glance, with so many parameters and so much code, it seems much more complex than the problem we discussed earlier, which might seem intimidating. However, these parameters merely control the start and end positions of arrays, and drawing a diagram can solve it.

Constructing a Binary Tree from Postorder and Inorder Traversal

Similar to the previous problem, this time we use the postorder and inorder traversal result arrays to reconstruct a binary tree. This is LeetCode problem 106: "Construct Binary Tree from Inorder and Postorder Traversal":

106. Construct Binary Tree from Inorder and Postorder Traversal | LeetCode | 🟠

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder and postorder consist of unique values.
Each value of postorder also appears in inorder.
inorder is guaranteed to be the inorder traversal of the tree.
postorder is guaranteed to be the postorder traversal of the tree.

The problem is from LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal.

java

// The function signature is as follows
TreeNode buildTree(int[] inorder, int[] postorder);

cpp

// The function signature is as follows
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder);

python

# The function signature is as follows
def buildTree(inorder: List[int], postorder: List[int]) -> TreeNode:

// The function signature is as follows
func buildTree(inorder []int, postorder []int) *TreeNode

javascript

// The function signature is as follows
var buildTree = function(inorder, postorder) {}

Similarly, let's look at the characteristics of postorder and inorder traversal:

java 🟢

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
    // postorder traversal
    postorder.add(root.val);
}

void traverse(TreeNode root) {
    traverse(root.left);
    // inorder traversal
    inorder.add(root.val);
    traverse(root.right);
}

cpp 🤖

void traverse(TreeNode* root) {
    if (root == NULL) return;
  
    traverse(root->left);
    traverse(root->right);
    
    // postorder traversal
    postorder.push_back(root->val);
}

void traverse(TreeNode* root) {
    if (root == NULL) return;
    
    traverse(root->left);
    
    // inorder traversal
    inorder.push_back(root->val);
    
    traverse(root->right);
}

python 🤖

def traverse(root):
    if root:
        traverse(root.left)
        traverse(root.right)
        # postorder traversal
        postorder.append(root.val)

def traverse(root):
    if root:
        traverse(root.left)
        # inorder traversal
        inorder.append(root.val)
        traverse(root.right)

go 🤖

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    traverse(root.Right)
    // postorder traversal
    postorder = append(postorder, root.Val)
}

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    // inorder traversal
    inorder = append(inorder, root.Val)
    traverse(root.Right)
}

javascript 🤖

var traverse = function(root) {
    if (root==null) { 
      return; 
    }
    traverse(root.left);
    traverse(root.right);
    // post-order traversal
    postorder.push(root.val);
}

var traverse = function(root) {
    if (root==null) { 
      return; 
    }
    traverse(root.left);
    // in-order traversal
    inorder.push(root.val);
    traverse(root.right);
}

The difference in traversal order leads to the following characteristics of element distribution in the postorder and inorder arrays:

The key difference between this problem and the previous one is that in postorder traversal, contrary to preorder, the root node corresponds to the last element of postorder.

The overall algorithm framework is very similar to the previous problem. We still write a helper function build:

java

class Solution {
    // Store the mapping from values to indices in the inorder array
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1,
                    postorder, 0, postorder.length - 1);
    }

    // Definition of the build function:
    // The postorder traversal array is postorder[postStart..postEnd],
    // The inorder traversal array is inorder[inStart..inEnd],
    // Construct the binary tree and return its root node
    TreeNode build(int[] inorder, int inStart, int inEnd,
                int[] postorder, int postStart, int postEnd) {
        // The value of the root node is the last element of the postorder traversal array
        int rootVal = postorder[postEnd];
        // The index of rootVal in the inorder traversal array
        int index = valToIndex.get(rootVal);

        TreeNode root = new TreeNode(rootVal);
        // Recursively construct the left and right subtrees
        root.left = build(inorder, ?, ?,
                        postorder, ?, ?);

        root.right = build(inorder, ?, ?,
                        postorder, ?, ?);
        return root;
    }
}

cpp

class Solution {
public:
    // store the mapping from value to index in inorder
    unordered_map<int, int> valToIndex;

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for (int i = 0; i < inorder.size(); i++) {
            valToIndex[inorder[i]] = i;
        }
        return build(inorder, 0, inorder.size() - 1,
                     postorder, 0, postorder.size() - 1);
    }

// definition of build function:
// postorder traversal array is postorder[postStart..postEnd],
// inorder traversal array is inorder[inStart..inEnd],
// construct the binary tree, return the root node of the tree
TreeNode* build(vector<int>& inorder, int inStart, int inEnd,
                vector<int>& postorder, int postStart, int postEnd) {
        // the value of the root node is the last element in the postorder array
        int rootVal = postorder[postEnd];
        // index of rootVal in the inorder array
        int index = valToIndex[rootVal];

        TreeNode* root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        root->left = build(inorder, ?, ?,
                           postorder, ?, ?);

        root->right = build(inorder, ?, ?,
                            postorder, ?, ?);
        return root;
    }
};

python

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        # store the mapping from value to index in inorder
        valToIndex = {val: idx for idx, val in enumerate(inorder)}

        # definition of build function:
        # postorder traversal array is postorder[postStart..postEnd],
        # inorder traversal array is inorder[inStart..inEnd],
        # construct the binary tree, return the root node of this tree
        def build(in_left, in_right, post_left, post_right):
            if in_left > in_right: return
            
            # the value of the root node is the last element of the postorder traversal array
            root_val = postorder[post_right]
            # the index of rootVal in the inorder traversal array
            index = valToIndex[root_val]

            root = TreeNode(root_val)
            # recursively construct the left and right subtrees
            size_left_subtree = index - in_left
            root.left = build(inorder, ?, ?,
                               postorder, ?, ?)
            root.right = build(inorder, ?, ?,
                                postorder, ?, ?)
            
            return root

        return build(0, len(inorder) - 1, 0, len(postorder) - 1)

func buildTree(inorder []int, postorder []int) *TreeNode {
    // store the mapping from value to index in inorder
    valToIndex := make(map[int]int)
    for i, v := range inorder {
        valToIndex[v] = i
    }

    // definition of build function:
    // postorder array is postorder[postStart..postEnd],
    // inorder array is inorder[inStart..inEnd],
    // construct the binary tree, return the root node of the tree
    var build func(inStart int, inEnd int, postStart int, postEnd int) *TreeNode
    build = func(inStart int, inEnd int, postStart int, postEnd int) *TreeNode {
        if inStart > inEnd {
            return nil
        }

        // the value of root node is the last element of postorder array
        rootVal := postorder[postEnd]
        // index of rootVal in inorder array
        index := valToIndex[rootVal]

        root := &TreeNode{Val: rootVal}
        // recursively construct the left and right subtrees
        root.Left = build(inorder, ?, ?,
                           postorder, ?, ?);
        root.Right = build(inorder, ?, ?,
                            postorder, ?, ?);

        return root
    }

    return build(0, len(inorder)-1, 0, len(postorder)-1)
}

javascript

var buildTree = function(inorder, postorder) {
    // store the mapping of values to indices in inorder
    var valToIndex = {};
    for (let i = 0; i < inorder.length; i++) {
        valToIndex[inorder[i]] = i;
    }

    // definition of the build function:
    // the postorder traversal array is postorder[postStart..postEnd],
    // the inorder traversal array is inorder[inStart..inEnd],
    // construct the binary tree and return the root node of this tree
    function build(inStart, inEnd, postStart, postEnd) {
        // if no elements to construct subtrees
        if (inStart > inEnd) {
            return null; 
        }

        // the value of the root node is the last element in the postorder traversal array
        let rootVal = postorder[postEnd];
        // the index of rootVal in the inorder traversal array
        let index = valToIndex[rootVal];
        
        var root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        root.left = build(inorder, ?, ?,
                           postorder, ?, ?);
        root.right = build(inorder, ?, ?,
                           postorder, ?, ?);
        
        return root;
    }
    return build(0, inorder.length - 1, 0, postorder.length - 1);
};

Now the states corresponding to postorder and inorder are as follows:

We can correctly fill in the indices at the question marks as shown in the above figure:

int leftSize = index - inStart;

root.left = build(inorder, inStart, index - 1,
                  postorder, postStart, postStart + leftSize - 1);

root.right = build(inorder, index + 1, inEnd,
                   postorder, postStart + leftSize, postEnd - 1);

In summary, the complete solution code can be written as follows:

java

class Solution {
    // store the mapping from value to index in inorder
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1,
                    postorder, 0, postorder.length - 1);
    }

    // Definition: the inorder array is inorder[inStart..inEnd],
    // the postorder array is postorder[postStart..postEnd],
    // the build function constructs this binary tree
    // and returns the root node of the binary tree
    TreeNode build(int[] inorder, int inStart, int inEnd,
                int[] postorder, int postStart, int postEnd) {

        if (inStart > inEnd) {
            return null;
        }
        // the value of the root node is the last element in the postorder array
        int rootVal = postorder[postEnd];
        // the index of rootVal in the inorder array
        int index = valToIndex.get(rootVal);
        // the number of nodes in the left subtree
        int leftSize = index - inStart;
        TreeNode root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        root.left = build(inorder, inStart, index - 1,
                         postorder, postStart, postStart + leftSize - 1);
        
        root.right = build(inorder, index + 1, inEnd,
                          postorder, postStart + leftSize, postEnd - 1);
        return root;
    }
}

cpp

class Solution {
    // store the mapping from value to index in inorder
    unordered_map<int, int> valToIndex;

public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for (int i = 0; i < inorder.size(); i++) {
            valToIndex[inorder[i]] = i;
        }
        return build(inorder, 0, inorder.size() - 1,
                     postorder, 0, postorder.size() - 1);
    }

    // Definition: the inorder array is inorder[inStart..inEnd],
    // the postorder array is postorder[postStart..postEnd],
    // the build function constructs this binary tree
    // and returns the root node of the binary tree
    TreeNode* build(vector<int>& inorder, int inStart, int inEnd,
                    vector<int>& postorder, int postStart, int postEnd) {

        if (inStart > inEnd) {
            return nullptr;
        }
        // the value of the root node is the last element in the postorder array
        int rootVal = postorder[postEnd];
        // the index of rootVal in the inorder array
        int index = valToIndex[rootVal];
        // the number of nodes in the left subtree
        int leftSize = index - inStart;
        TreeNode* root = new TreeNode(rootVal);

        // recursively construct the left and right subtrees
        root->left = build(inorder, inStart, index - 1,
                           postorder, postStart, postStart + leftSize - 1);
        
        root->right = build(inorder, index + 1, inEnd,
                            postorder, postStart + leftSize, postEnd - 1);
        return root;
    }
};

python

class Solution:
    # store the mapping from value to index in inorder
    val_to_index = {}

    def buildTree(self, inorder, postorder):
        for i in range(len(inorder)):
            self.val_to_index[inorder[i]] = i
        return self.build(inorder, 0, len(inorder) - 1,
                          postorder, 0, len(postorder) - 1)

    # Definition: the inorder array is inorder[inStart..inEnd],
    # the postorder array is postorder[postStart..postEnd],
    # the build function constructs this binary tree
    # and returns the root node of the binary tree
    def build(self, inorder, in_start, in_end,
              postorder, post_start, post_end):

        if in_start > in_end:
            return None
        # the value of the root node is the last element in the postorder array
        root_val = postorder[post_end]
        # the index of rootVal in the inorder array
        index = self.val_to_index[root_val]
        # the number of nodes in the left subtree
        left_size = index - in_start
        root = TreeNode(root_val) 
        # recursively construct the left and right subtrees
        root.left = self.build(inorder, in_start, index - 1,
                               postorder, post_start, post_start + left_size - 1)
        
        root.right = self.build(inorder, index + 1, in_end,
                                postorder, post_start + left_size, post_end - 1)
        return root

func buildTree(inorder []int, postorder []int) *TreeNode {
    // store the mapping from value to index in inorder
    indexMap := make(map[int]int)
    for i, v := range inorder {
        indexMap[v] = i
    }
    return build(inorder, 0, len(inorder)-1, postorder, 0, len(postorder)-1, indexMap)
}


// Definition of the build function:
// The postorder traversal array is postorder[postStart..postEnd],
// The inorder traversal array is inorder[inStart..inEnd],
// Construct the binary tree and return its root node.
func build(inorder []int, inStart int, inEnd int, postorder []int, postStart int, postEnd int, indexMap map[int]int) *TreeNode {
    if inStart > inEnd {
        return nil
    }
    // the value of the root node is the last element in the postorder array
    rootVal := postorder[postEnd]
    // the index of rootVal in the inorder array
    index := indexMap[rootVal]
    // the number of nodes in the left subtree
    leftSize := index - inStart
    
    root := &TreeNode{Val: rootVal}
    // recursively construct the left and right subtrees
    root.Left = build(inorder, inStart, index-1, postorder, postStart, postStart+leftSize-1, indexMap)
    root.Right = build(inorder, index+1, inEnd, postorder, postStart+leftSize, postEnd-1, indexMap)
    
    return root
}

javascript

var buildTree = function(inorder, postorder) {
    // store the mapping from value to index in inorder
    let valToIndex = new Map();
    for (let i = 0; i < inorder.length; i++) {
        valToIndex.set(inorder[i], i);
    }

    // Definition: the inorder array is inorder[inStart..inEnd],
    // the postorder array is postorder[postStart..postEnd],
    // the build function constructs this binary tree
    // and returns the root node of the binary tree
    var build = function(inorder, inStart, inEnd, postorder, postStart, postEnd) {
        if (inStart > inEnd) {
            return null;
        }
        // the value of the root node is the last element in the postorder array
        let rootVal = postorder[postEnd];
        // the index of rootVal in the inorder array
        let index = valToIndex.get(rootVal);
        // the number of nodes in the left subtree
        let leftSize = index - inStart;
        let root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        root.left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1);
        root.right = build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
        return root;
    }

    return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
};

Algorithm Visualization

With the foundation laid by the previous problem, this one is quickly resolved. The only change is that rootVal becomes the last element, and some adjustments to the recursive function parameters. As long as you understand the characteristics of binary trees, it's not difficult to write.

Constructing a Binary Tree from Postorder and Preorder Traversal Results

This is LeetCode Problem 889: "Construct Binary Tree from Preorder and Postorder Traversal". You are given the preorder and postorder traversal results of a binary tree and asked to reconstruct the tree's structure.

The function signature is as follows:

java 🟢

TreeNode constructFromPrePost(int[] preorder, int[] postorder);

cpp 🤖

TreeNode* constructFromPrePost(vector<int>& preOrder, vector<int>& postOrder);

python 🤖

from typing import List

def constructFromPrePost(preorder: List[int], postorder: List[int]) -> TreeNode:

go 🤖

func constructFromPrePost(preorder []int, postorder []int) *TreeNode

javascript 🤖

var constructFromPrePost = function(preorder, postorder) {}

This problem has a fundamental difference from the previous two:

With preorder and inorder or postorder and inorder traversal results, you can determine a unique original binary tree. However, using preorder and postorder results alone cannot determine a unique original binary tree.

The problem statement also mentions that if there are multiple possible reconstruction results, you can return any one of them.

Why is this the case? As we have discussed, the strategy for constructing a binary tree is quite straightforward: first, identify the root node, then recursively construct the left and right subtrees.

In the previous two problems, you could identify the root node using the preorder or postorder traversal results, and then determine the left and right subtrees using the inorder traversal results (the problem states that there are no nodes with the same val in the tree).

In this problem, you can determine the root node, but you cannot precisely identify which nodes belong to the left or right subtrees.

For example, consider this input:

preorder = [1,2,3], postorder = [3,2,1]

Both of the following trees satisfy the conditions, but clearly, their structures are different:

That said, reconstructing a binary tree using postorder and preorder results involves a logic similar to the previous problems, where you control the indices of the left and right subtrees to construct them:

1. First, determine the root node's value using the first element of the preorder result or the last element of the postorder result.

2. Then, take the second element of the preorder result as the root node's value of the left subtree.

3. Locate the value of the left subtree's root node in the postorder result to determine the index boundaries for the left subtree, which in turn allows you to determine the index boundaries for the right subtree, and recursively construct the left and right subtrees.

See the code for details.

java 🟢

class Solution {
    // Store the mapping from value to index in postorder
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for (int i = 0; i < postorder.length; i++) {
            valToIndex.put(postorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1,
                    postorder, 0, postorder.length - 1);
    }

    // Definition: build the binary tree from
    // preorder[preStart..preEnd] and postorder[postStart..postEnd]
    // and return the root node.
    TreeNode build(int[] preorder, int preStart, int preEnd,
                   int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }

        // The value of the root node is the first element in the preorder array
        int rootVal = preorder[preStart];
        // The value of root.left is the second element in the preorder array
        // The key to constructing a binary tree from preorder and postorder is to determine the
        // element range of left and right subtrees through the root of the left subtree
        // in preorder and postorder
        int leftRootVal = preorder[preStart + 1];
        // The index of leftRootVal in the postorder array
        int index = valToIndex.get(leftRootVal);
        // The number of elements in the left subtree
        int leftSize = index - postStart + 1;

        // First, construct the current root node
        TreeNode root = new TreeNode(rootVal);
        // Recursively construct the left and right subtrees
        // Derive the index boundaries of the left and right subtrees based on
        // the root index and the number of elements in the left subtree
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                postorder, postStart, index);
        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                postorder, index + 1, postEnd - 1);

        return root;
    }
}

cpp 🤖

class Solution {
    // store the mapping of values to indices in postorder
    unordered_map<int, int> valToIndex;

public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        for (int i = 0; i < postorder.size(); i++) {
            valToIndex[postorder[i]] = i;
        }
        return build(preorder, 0, preorder.size() - 1,
                    postorder, 0, postorder.size() - 1);
    }

    // Definition: construct a binary tree based on
    // preorder[preStart..preEnd] and postorder[postStart..postEnd]
    // and return the root node.
    TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                   vector<int>& postorder, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return nullptr;
        }
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }

        // the value of the root node corresponds to the first element of the preorder array
        int rootVal = preorder[preStart];
        // root.left's value is the second element of the preorder array
        // the key to constructing a binary tree using preorder and postorder is
        // to determine the element range of the left and right subtrees
        // in preorder and postorder based on the root node of the left subtree
        int leftRootVal = preorder[preStart + 1];
        // the index of leftRootVal in the postorder array
        int index = valToIndex[leftRootVal];
        // the number of elements in the left subtree
        int leftSize = index - postStart + 1;

        // first construct the current root node
        TreeNode* root = new TreeNode(rootVal);
        // recursively construct the left and right subtrees
        // deduce the index boundaries of the left and right subtrees based on the
        // root node index and the number of elements of the left subtree
        root->left = build(preorder, preStart + 1, preStart + leftSize,
                postorder, postStart, index);
        root->right = build(preorder, preStart + leftSize + 1, preEnd,
                postorder, index + 1, postEnd - 1);

        return root;
    }
};

python 🤖

class Solution:
    # store the mapping from value to index in postorder
    valToIndex = dict()

    def constructFromPrePost(self, preorder, postorder):
        for i in range(len(postorder)):
            self.valToIndex[postorder[i]] = i
        return self.build(preorder, 0, len(preorder) - 1,
                          postorder, 0, len(postorder) - 1)

    # definition: construct the binary tree based on
    # preorder[preStart..preEnd] and postorder[postStart..postEnd]
    # build the binary tree and return the root node.
    def build(self, preorder, preStart, preEnd,
              postorder, postStart, postEnd):
        if preStart > preEnd:
            return None
        if preStart == preEnd:
            return TreeNode(preorder[preStart])

        # the value of the root node is the first element in the preorder array
        rootVal = preorder[preStart]
        # the value of root.left is the second element in preorder
        # the key to constructing the binary tree using preorder and postorder is to determine the
        # element range of the left and right subtrees using the root node of the left subtree
        # determine the element range of the left and right subtrees in preorder and postorder
        leftRootVal = preorder[preStart + 1]
        # the index of leftRootVal in the postorder array
        index = self.valToIndex[leftRootVal]
        # the number of elements in the left subtree
        leftSize = index - postStart + 1
     
        # first construct the current root node
        root = TreeNode(rootVal) 
        # recursively construct the left and right subtrees
        # derive the index boundaries of the left and right subtrees based on the
        # root node index and the number of elements in the left subtree
        root.left = self.build(preorder, preStart + 1, preStart + leftSize,
                               postorder, postStart, index)
        root.right = self.build(preorder, preStart + leftSize + 1, preEnd,
                                postorder, index + 1, postEnd - 1)

        return root

go 🤖

func constructFromPrePost(preorder []int, postorder []int) *TreeNode{
    // store the mapping from values to indices in postorder
    valToIndex := make(map[int]int)

    for i := 0; i < len(postorder); i++ {
        valToIndex[postorder[i]] = i
    }

    // definition: build a binary tree based on
    // preorder[preStart..preEnd] and postorder[postStart..postEnd], and return the root node
    var build func(preorder []int, preStart, preEnd int, postorder []int, postStart, postEnd int) *TreeNode
	build = func(preorder []int, preStart, preEnd int, postorder []int, postStart, postEnd int) *TreeNode {    
    	if preStart > preEnd {
        	return nil
    	}
    	if preStart == preEnd {
        	return &TreeNode{
				Val:   preorder[preStart],
				Left:  nil,
				Right: nil,
			}
    	}

    	// the value of the root node corresponds to the first element in the preorder array
    	rootVal := preorder[preStart]
    	// the value of root.left is the second element in the preorder array
    	// the key to constructing a binary tree from preorder and postorder traversals is
// determining the element ranges of the left and right subtrees via the root node of the left subtree
    	// determine the element ranges of the left and right subtrees in preorder and postorder
    	leftRootVal := preorder[preStart + 1]
    	// the index of leftRootVal in the postorder array
    	index := valToIndex[leftRootVal]
    	// the number of elements in the left subtree
    	leftSize := index - postStart + 1

    	// first construct the current root node
    	root := &TreeNode{
			Val:   rootVal,
			Left:  nil,
			Right: nil,
		}

    	// recursively construct the left and right subtrees
    	// deduce the index boundaries of the left and right subtrees based on
// the root node index and the number of elements in the left subtree
    	root.Left = build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, index)
    	root.Right = build(preorder, preStart + leftSize + 1, preEnd, postorder, index + 1, postEnd - 1)

    	return root
    }

    return build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)
}

javascript 🤖

var constructFromPrePost = function(preorder, postorder) {
    // store the mapping from values to indices in postorder

    const valToIndex = {};
    for (let i = 0; i < postorder.length; i++) {
        valToIndex[postorder[i]] = i;
    }

// definition: build the binary tree based on
// preorder[preStart..preEnd] and postorder[postStart..postEnd] and return the root node
var build = function(preorder, preStart, preEnd, postorder, postStart, postEnd) {
    if (preStart > preEnd) {
        return null;
    }
    if (preStart === preEnd) {
        return new TreeNode(preorder[preStart]);
    }

    // the value of the root node corresponds to the first element of the preorder array
    let rootVal = preorder[preStart];
    // the value of root.left is the second element of the preorder array
    // the key to constructing the binary tree through preorder and
    // postorder traversal lies in the root node of the left subtree
    // determine the element ranges of the left and right subtrees in preorder and postorder
    let leftRootVal = preorder[preStart + 1];
    // the index of leftRootVal in the postorder array
    let index = valToIndex[leftRootVal];
    // the number of elements in the left subtree
    let leftSize = index - postStart + 1;

    // first, construct the current root node
    let root = new TreeNode(rootVal);
    // recursively construct the left and right subtrees
    // deduce the index boundaries of the left and right subtrees based on
    // the root node index and the number of elements of the left subtree
    root.left = build(preorder, preStart + 1, preStart + leftSize,
            postorder, postStart, index);
    root.right = build(preorder, preStart + leftSize + 1, preEnd,
            postorder, index + 1, postEnd - 1);

    return root;
};

    return build(preorder, 0, preorder.length - 1,
                    postorder, 0, postorder.length - 1);
};

Algorithm Visualization

The code is very similar to the previous two problems. Let's think about why the binary tree reconstructed from preorder and postorder traversal results might not be unique.

The key lies in this line:

int leftRootVal = preorder[preStart + 1];

We assume that the second element in the preorder traversal is the root of the left subtree. However, the left subtree could actually be null, making this element the root of the right subtree instead. Since we can't determine this with certainty, the final result is not unique.

Thus, the problem of reconstructing a binary tree from preorder and postorder traversal results is resolved.

To echo the previous discussion, constructing a binary tree usually involves a "divide and conquer" approach: constructing the entire tree = root node + constructing the left subtree + constructing the right subtree. First, find the root node, then use the root node's value to identify the elements of the left and right subtrees, and recursively construct the left and right subtrees.

Do you now understand the subtlety of this process?

Related Problems

You can install my Chrome extension then open the link.

LeetCode	Difficulty
1008. Construct Binary Search Tree from Preorder Traversal	🟠

Binary Tree in Action (Construction)

105. Construct Binary Tree from Preorder and Inorder Traversal https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

106. Construct Binary Tree from Inorder and Postorder Traversal https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal

654. Maximum Binary Tree https://leetcode.com/problems/maximum-binary-tree

889. Construct Binary Tree from Preorder and Postorder Traversal https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal

Constructing Maximum Binary Tree

Constructing a Binary Tree from Preorder and Inorder Traversal

Constructing a Binary Tree from Postorder and Inorder Traversal

Constructing a Binary Tree from Postorder and Preorder Traversal Results