Skip to content

12.3   Building a binary tree

Question

Given a binary tree's preorder traversal preorder and inorder traversal inorder, reconstruct the tree and return its root node. Assume that all node values are distinct, as shown in Figure 12-5.

Example input for reconstructing a binary tree

Figure 12-5   Example input for reconstructing a binary tree

1.   Identifying a divide-and-conquer problem

Reconstructing a binary tree from preorder and inorder is a typical divide-and-conquer problem.

  • The problem can be divided: We can split the original problem into two subproblems, building the left subtree and building the right subtree, plus one operation: initializing the root node. Each subtree can be divided in the same way into smaller subtrees, until we reach the smallest subproblem, an empty subtree.
  • The subproblems are independent: The left and right subtrees are independent and do not overlap. To build the left subtree, we need only the portions of the preorder and inorder traversals corresponding to it. The same applies to the right subtree.
  • The subproblem solutions can be combined: Once we have built the left and right subtrees, we can attach them to the root to obtain the solution to the original problem.

2.   Dividing the subtrees

The analysis above shows that divide and conquer applies, but how do we use preorder and inorder to separate the left and right subtrees?

By definition, both preorder and inorder consist of three parts.

  • Preorder: [ root | left subtree | right subtree ]. For the tree above, this is [ 3 | 9 | 2 1 7 ].
  • Inorder: [ left subtree | root | right subtree ]. For the tree above, this is [ 9 | 3 | 1 2 7 ].

Using the example above, we can divide the traversals with the steps shown in Figure 12-6.

  1. The first element in the preorder traversal, 3, is the root value.
  2. Find the index of root value 3 in inorder, then use it to divide inorder into [ 9 | 3 | 1 2 7 ].
  3. This division of inorder tells us that the left and right subtrees have 1 and 3 nodes, respectively, allowing us to divide preorder into [ 3 | 9 | 2 1 7 ].

Separating subtrees in preorder and inorder traversals

Figure 12-6   Separating subtrees in preorder and inorder traversals

3.   Describing subtree intervals with variables

Using this method, we have identified the index intervals for the root, left subtree, and right subtree in preorder and inorder. We need a few pointer variables to describe these intervals.

  • Let \(i\) be the index of the current tree's root in preorder.
  • Let \(m\) be the index of the current tree's root in inorder.
  • Let \([l, r]\) be the interval occupied by the current tree in inorder.

As shown in Table 12-1, these variables describe the root index in preorder and each subtree's interval in inorder.

Table 12-1   Root and subtree indices in preorder and inorder traversals

Root index in preorder Subtree interval in inorder
Current tree \(i\) \([l, r]\)
Left subtree \(i + 1\) \([l, m-1]\)
Right subtree \(i + 1 + (m - l)\) \([m+1, r]\)

The term \((m-l)\) in the right subtree's root index is the number of nodes in the left subtree. Figure 12-7 helps illustrate this.

Index intervals for the root and the left and right subtrees

Figure 12-7   Index intervals for the root and the left and right subtrees

4.   Code implementation

To find \(m\) efficiently, we use a hash table hmap mapping each element of inorder to its index:

build_tree.py
def dfs(
    preorder: list[int],
    inorder_map: dict[int, int],
    i: int,
    l: int,
    r: int,
) -> TreeNode | None:
    """Build a binary tree: divide and conquer"""
    # Stop when the subtree interval is empty
    if r - l < 0:
        return None
    # Initialize the root node
    root = TreeNode(preorder[i])
    # Look up m to separate the left and right subtrees
    m = inorder_map[preorder[i]]
    # Subproblem: build the left subtree
    root.left = dfs(preorder, inorder_map, i + 1, l, m - 1)
    # Subproblem: build the right subtree
    root.right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r)
    # Return the root node
    return root

def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
    """Build a binary tree"""
    # Initialize a hash table mapping each element in inorder to its index
    inorder_map = {val: i for i, val in enumerate(inorder)}
    root = dfs(preorder, inorder_map, 0, 0, len(inorder) - 1)
    return root
build_tree.cpp
/* Build a binary tree: divide and conquer */
TreeNode *dfs(vector<int> &preorder, unordered_map<int, int> &inorderMap, int i, int l, int r) {
    // Stop when the subtree interval is empty
    if (r - l < 0)
        return NULL;
    // Initialize the root node
    TreeNode *root = new TreeNode(preorder[i]);
    // Look up m to separate the left and right subtrees
    int m = inorderMap[preorder[i]];
    // Subproblem: build the left subtree
    root->left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // Subproblem: build the right subtree
    root->right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // Return the root node
    return root;
}

/* Build a binary tree */
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    // Initialize a hash table mapping each element in inorder to its index
    unordered_map<int, int> inorderMap;
    for (int i = 0; i < inorder.size(); i++) {
        inorderMap[inorder[i]] = i;
    }
    TreeNode *root = dfs(preorder, inorderMap, 0, 0, inorder.size() - 1);
    return root;
}
build_tree.java
/* Build a binary tree: divide and conquer */
TreeNode dfs(int[] preorder, Map<Integer, Integer> inorderMap, int i, int l, int r) {
    // Stop when the subtree interval is empty
    if (r - l < 0)
        return null;
    // Initialize the root node
    TreeNode root = new TreeNode(preorder[i]);
    // Look up m to separate the left and right subtrees
    int m = inorderMap.get(preorder[i]);
    // Subproblem: build the left subtree
    root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // Subproblem: build the right subtree
    root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // Return the root node
    return root;
}

/* Build a binary tree */
TreeNode buildTree(int[] preorder, int[] inorder) {
    // Initialize a hash table mapping each element in inorder to its index
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    TreeNode root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
    return root;
}
build_tree.cs
/* Build a binary tree: divide and conquer */
TreeNode? DFS(int[] preorder, Dictionary<int, int> inorderMap, int i, int l, int r) {
    // Stop when the subtree interval is empty
    if (r - l < 0)
        return null;
    // Initialize the root node
    TreeNode root = new(preorder[i]);
    // Look up m to separate the left and right subtrees
    int m = inorderMap[preorder[i]];
    // Subproblem: build the left subtree
    root.left = DFS(preorder, inorderMap, i + 1, l, m - 1);
    // Subproblem: build the right subtree
    root.right = DFS(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // Return the root node
    return root;
}

/* Build a binary tree */
TreeNode? BuildTree(int[] preorder, int[] inorder) {
    // Initialize a hash table mapping each element in inorder to its index
    Dictionary<int, int> inorderMap = [];
    for (int i = 0; i < inorder.Length; i++) {
        inorderMap.TryAdd(inorder[i], i);
    }
    TreeNode? root = DFS(preorder, inorderMap, 0, 0, inorder.Length - 1);
    return root;
}
build_tree.go
/* Build a binary tree: divide and conquer */
func dfsBuildTree(preorder []int, inorderMap map[int]int, i, l, r int) *TreeNode {
    // Stop when the subtree interval is empty
    if r-l < 0 {
        return nil
    }
    // Initialize the root node
    root := NewTreeNode(preorder[i])
    // Look up m to separate the left and right subtrees
    m := inorderMap[preorder[i]]
    // Subproblem: build the left subtree
    root.Left = dfsBuildTree(preorder, inorderMap, i+1, l, m-1)
    // Subproblem: build the right subtree
    root.Right = dfsBuildTree(preorder, inorderMap, i+1+m-l, m+1, r)
    // Return the root node
    return root
}

/* Build a binary tree */
func buildTree(preorder, inorder []int) *TreeNode {
    // Initialize a hash table mapping each element in inorder to its index
    inorderMap := make(map[int]int, len(inorder))
    for i := 0; i < len(inorder); i++ {
        inorderMap[inorder[i]] = i
    }

    root := dfsBuildTree(preorder, inorderMap, 0, 0, len(inorder)-1)
    return root
}
build_tree.swift
/* Build a binary tree: divide and conquer */
func dfs(preorder: [Int], inorderMap: [Int: Int], i: Int, l: Int, r: Int) -> TreeNode? {
    // Stop when the subtree interval is empty
    if r - l < 0 {
        return nil
    }
    // Initialize the root node
    let root = TreeNode(x: preorder[i])
    // Look up m to separate the left and right subtrees
    let m = inorderMap[preorder[i]]!
    // Subproblem: build the left subtree
    root.left = dfs(preorder: preorder, inorderMap: inorderMap, i: i + 1, l: l, r: m - 1)
    // Subproblem: build the right subtree
    root.right = dfs(preorder: preorder, inorderMap: inorderMap, i: i + 1 + m - l, l: m + 1, r: r)
    // Return the root node
    return root
}

/* Build a binary tree */
func buildTree(preorder: [Int], inorder: [Int]) -> TreeNode? {
    // Initialize a hash table mapping each element in inorder to its index
    let inorderMap = inorder.enumerated().reduce(into: [:]) { $0[$1.element] = $1.offset }
    return dfs(preorder: preorder, inorderMap: inorderMap, i: inorder.startIndex, l: inorder.startIndex, r: inorder.endIndex - 1)
}
build_tree.js
/* Build a binary tree: divide and conquer */
function dfs(preorder, inorderMap, i, l, r) {
    // Stop when the subtree interval is empty
    if (r - l < 0) return null;
    // Initialize the root node
    const root = new TreeNode(preorder[i]);
    // Look up m to separate the left and right subtrees
    const m = inorderMap.get(preorder[i]);
    // Subproblem: build the left subtree
    root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // Subproblem: build the right subtree
    root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // Return the root node
    return root;
}

/* Build a binary tree */
function buildTree(preorder, inorder) {
    // Initialize a hash table mapping each element in inorder to its index
    let inorderMap = new Map();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }
    const root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
    return root;
}
build_tree.ts
/* Build a binary tree: divide and conquer */
function dfs(
    preorder: number[],
    inorderMap: Map<number, number>,
    i: number,
    l: number,
    r: number
): TreeNode | null {
    // Stop when the subtree interval is empty
    if (r - l < 0) return null;
    // Initialize the root node
    const root: TreeNode = new TreeNode(preorder[i]);
    // Look up m to separate the left and right subtrees
    const m = inorderMap.get(preorder[i]);
    // Subproblem: build the left subtree
    root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // Subproblem: build the right subtree
    root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // Return the root node
    return root;
}

/* Build a binary tree */
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    // Initialize a hash table mapping each element in inorder to its index
    let inorderMap = new Map<number, number>();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }
    const root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
    return root;
}
build_tree.dart
/* Build a binary tree: divide and conquer */
TreeNode? dfs(
  List<int> preorder,
  Map<int, int> inorderMap,
  int i,
  int l,
  int r,
) {
  // Stop when the subtree interval is empty
  if (r - l < 0) {
    return null;
  }
  // Initialize the root node
  TreeNode? root = TreeNode(preorder[i]);
  // Look up m to separate the left and right subtrees
  int m = inorderMap[preorder[i]]!;
  // Subproblem: build the left subtree
  root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
  // Subproblem: build the right subtree
  root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
  // Return the root node
  return root;
}

/* Build a binary tree */
TreeNode? buildTree(List<int> preorder, List<int> inorder) {
  // Initialize a hash table mapping each element in inorder to its index
  Map<int, int> inorderMap = {};
  for (int i = 0; i < inorder.length; i++) {
    inorderMap[inorder[i]] = i;
  }
  TreeNode? root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
  return root;
}
build_tree.rs
/* Build a binary tree: divide and conquer */
fn dfs(
    preorder: &[i32],
    inorder_map: &HashMap<i32, i32>,
    i: i32,
    l: i32,
    r: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    // Stop when the subtree interval is empty
    if r - l < 0 {
        return None;
    }
    // Initialize the root node
    let root = TreeNode::new(preorder[i as usize]);
    // Look up m to separate the left and right subtrees
    let m = inorder_map.get(&preorder[i as usize]).unwrap();
    // Subproblem: build the left subtree
    root.borrow_mut().left = dfs(preorder, inorder_map, i + 1, l, m - 1);
    // Subproblem: build the right subtree
    root.borrow_mut().right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r);
    // Return the root node
    Some(root)
}

/* Build a binary tree */
fn build_tree(preorder: &[i32], inorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
    // Initialize a hash table mapping each element in inorder to its index
    let mut inorder_map: HashMap<i32, i32> = HashMap::new();
    for i in 0..inorder.len() {
        inorder_map.insert(inorder[i], i as i32);
    }
    let root = dfs(preorder, &inorder_map, 0, 0, inorder.len() as i32 - 1);
    root
}
build_tree.c
/* Build a binary tree: divide and conquer */
TreeNode *dfs(int *preorder, int *inorderMap, int i, int l, int r, int size) {
    // Stop when the subtree interval is empty
    if (r - l < 0)
        return NULL;
    // Initialize the root node
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = preorder[i];
    root->left = NULL;
    root->right = NULL;
    // Look up m to separate the left and right subtrees
    int m = inorderMap[preorder[i]];
    // Subproblem: build the left subtree
    root->left = dfs(preorder, inorderMap, i + 1, l, m - 1, size);
    // Subproblem: build the right subtree
    root->right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r, size);
    // Return the root node
    return root;
}

/* Build a binary tree */
TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize) {
    // Initialize a lookup array mapping inorder values to their indices
    int *inorderMap = (int *)malloc(sizeof(int) * MAX_SIZE);
    for (int i = 0; i < inorderSize; i++) {
        inorderMap[inorder[i]] = i;
    }
    TreeNode *root = dfs(preorder, inorderMap, 0, 0, inorderSize - 1, inorderSize);
    free(inorderMap);
    return root;
}
build_tree.kt
/* Build a binary tree: divide and conquer */
fun dfs(
    preorder: IntArray,
    inorderMap: Map<Int?, Int?>,
    i: Int,
    l: Int,
    r: Int
): TreeNode? {
    // Stop when the subtree interval is empty
    if (r - l < 0) return null
    // Initialize the root node
    val root = TreeNode(preorder[i])
    // Look up m to separate the left and right subtrees
    val m = inorderMap[preorder[i]]!!
    // Subproblem: build the left subtree
    root.left = dfs(preorder, inorderMap, i + 1, l, m - 1)
    // Subproblem: build the right subtree
    root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r)
    // Return the root node
    return root
}

/* Build a binary tree */
fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
    // Initialize a hash table mapping each element in inorder to its index
    val inorderMap = HashMap<Int?, Int?>()
    for (i in inorder.indices) {
        inorderMap[inorder[i]] = i
    }
    val root = dfs(preorder, inorderMap, 0, 0, inorder.size - 1)
    return root
}
build_tree.rb
### Build a binary tree: divide and conquer ###
def dfs(preorder, inorder_map, i, l, r)
  # Stop when the subtree interval is empty
  return if r - l < 0

  # Initialize the root node
  root = TreeNode.new(preorder[i])
  # Look up m to separate the left and right subtrees
  m = inorder_map[preorder[i]]
  # Subproblem: build the left subtree
  root.left = dfs(preorder, inorder_map, i + 1, l, m - 1)
  # Subproblem: build the right subtree
  root.right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r)

  # Return the root node
  root
end

### Build a binary tree ###
def build_tree(preorder, inorder)
  # Initialize a hash table mapping each element in inorder to its index
  inorder_map = {}
  inorder.each_with_index { |val, i| inorder_map[val] = i }
  dfs(preorder, inorder_map, 0, 0, inorder.length - 1)
end
Visualize execution

Figure 12-8 shows the recursive reconstruction process. Nodes are created during recursive descent, while edges (references) are established as the recursive calls return.

Recursive process for building a binary tree

built_tree_step2

built_tree_step3

built_tree_step4

built_tree_step5

built_tree_step6

built_tree_step7

built_tree_step8

built_tree_step9

Figure 12-8   Recursive process for building a binary tree

Figure 12-9 shows how preorder and inorder are divided in each recursive call.

Division within each recursive call

Figure 12-9   Division within each recursive call

For a tree with \(n\) nodes, initializing each node (executing one call to dfs()) takes \(O(1)\) time. The overall time complexity is therefore \(O(n)\).

The hash table maps inorder elements to indices, requiring \(O(n)\) space. In the worst case, the binary tree degenerates into a linked list, and the recursion depth reaches \(n\), using \(O(n)\) space for stack frames. The overall space complexity is therefore \(O(n)\).

Share your insights, questions, or suggestions in the comments