Construct Binary Tree from Inorder and Postorder Traversal

Building a binary tree from its inorder and postorder traversals can be done through a recursive approach.

1. Understand the Traversal Information:

   • In the inorder traversal, left subtree nodes come before the root, and right subtree nodes come after the root.
   • In the postorder traversal, the last element is the root of the current subtree, followed by the nodes of the left and right subtrees.

2. Start the Process:

   • Start by picking the last element from the postorder array as the root.
   • Find that root value in the inorder array. Elements on the left of this value in the inorder array form the left subtree, and elements on the right form the right subtree.
   • Recursively repeat the process for the left and right subtrees.

3. Implement the Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder or not postorder:
            return None

        # The last element in postorder is the root
        root_val = postorder.pop()
        root = TreeNode(root_val)

        # Find the index of root in inorder
        root_idx = inorder.index(root_val)

        # Build the right subtree
        root.right = self.buildTree(inorder[root_idx + 1:], postorder)

        # Build the left subtree
        root.left = self.buildTree(inorder[:root_idx], postorder)

        return root

Key Insights:

• Since the root is the last element in postorder, we start building the tree from the end of the postorder list.
• The inorder list is used to determine the boundary of the left and right subtrees.
• We build the right subtree first because in postorder, the right subtree elements appear before the left subtree elements.

The time complexity of this code is (O(n^2)) because the index method takes (O(n)) time, and it is called (n) times. This can be optimized to (O(n)) by using a hash table to store the index of each element in the inorder array. The space complexity is (O(n)).

inorder = [-,-,-,-,-] postorder = [-,-,-,-,-]

Keep track of number of nodes we have created so far, stop when we have the same number of nodes as the input array.

Where does the root go when we do a post order traversal? Does the root always go to the last position for post order traversal? Yes. How do you decide the left child? We found the root as 3, look in the inorder and search for the root, the number left to the root is the left child.

How do you decide the right child? So for the right child, look in the post order and find the value to the left of the root. This is the right child.

In the inorder, the left value is 15 for 20 so 15 is the left child. In the postorder, the left value of 20 is 7, so 7 is the right child.

How do we know when we need to terminate?

Total number of nodes - number of leaf nodes 5 - 3 = 2 We need to know the number of leaves? How do we identify the leaves from the inorder and postorder arrays.

Return the TreeNode instance for 3.

Problem Definition

Define the Terms

Binary Tree: A tree that has at most two children (left and right child.

Define the Interface

  Input: array of integers, array of integers
  Output: TreeNode instance of binary tree

Identify Implicit Inputs

Define the Goal

Construct and return the binary tree

Identify the 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.

Construct a Binary Tree

1. Who is the root of the binary tree?
2. A value for left and right children for the root.

Who is the root? What is its left child? What is its right child?

Determine the Scope

• List assumptions
• Define boundaries of the problem

Search the Problem Space

• Look for clues in the problem statement

Classify the Problem

• Decontextualize the Problem

• Can you think of this problem in a different way?

• Can you reframe it?

Problem Representation

• Analyze the Input and Output

• Analyze the Examples

Solve the Problem by Hand

Recognize the Pattern

Identify the Invariants

Brainstorm Solutions

• Brute Force Approach

• Shortcomings

Recursive Approach Base Case: Not an edge case but a way to terminate recursion.

Helper function parameters: inorder,

left half: 0..i-1 (new inorder array) right half: i+1..size-1

Unit of Decomposition is variable in this case.

When the inorder array becomes empty, we terminate recursion.

Write two recursive calls (one for the left and one for the right)

Unit of Work

• Create an instance of TreeNode
• Create the left subtree (subproblem)
• Create the right subtree (subproblem)
• Root must be linked to the left subtree
• Root must be linked to the right subtree

What is the contract between the parent and the child? Output of the subproblems is a binary tree (left and right subtree) We can only get the constructed left and right subtrees after the recursive calls return.

So the links for the left and right must be done after the recursve calls return.

root.left = recur([0..i-1]) root.right = recur([i+1..size-1])

As we go from the leaves to the root. We are mixing declarative and imperative programming in one program.

What should we return from the helper function? We need to return the root object. Counter variable can be used to terminate the recursion.

• Evaluate and Select Approach

Analyze Time and Space Complexity

• Time: O( )
• Space: O( )

Outline the Solution

Key Takeaways

Reflect

• What went right?

• What went wrong?

• What can we improve next time?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {Integer[]} inorder
# @param {Integer[]} postorder
# @return {TreeNode}
def build_tree(inorder, postorder)
  postsize = postorder.size
  if inorder.empty?
      return
  end
   node_val = postorder.last
    node_index = inorder.index(node_val)
    node = TreeNode.new(node_val)
    
    if node_index && node_index > 0
        node.left = build_tree(inorder[0..node_index-1], postorder[0..node_index-1])
    end
    if node_index && node_index < inorder.size - 1 
        node.right = build_tree(inorder[node_index+1..-1], postorder[node_index...postsize-1])
    end
    
    node
end

inorder = [-,-,-,-,-] postorder = [-,-,-,-,-]

Keep track of number of nodes we have created so far, stop when we have the same number of nodes as the input array.

Where does the root go when we do a post order traversal? Does the root always go to the last position for post order traversal? Yes. How do you decide the left child? We found the root as 3, look in the inorder and search for the root, the number left to the root is the left child.

How do you decide the right child? So for the right child, look in the post order and find the value to the left of the root. This is the right child.

In the inorder, the left value is 15 for 20 so 15 is the left child. In the postorder, the left value of 20 is 7, so 7 is the right child.

How do we know when we need to terminate?

Total number of nodes - number of leaf nodes 5 - 3 = 2 We need to know the number of leaves? How do we identify the leaves from the inorder and postorder arrays.

Return the TreeNode instance for 3.

Problem Definition

Define the Terms

Binary Tree: A tree that has at most two children (left and right child.

Define the Interface

  Input: array of integers, array of integers
  Output: TreeNode instance of binary tree

Identify Implicit Inputs

Define the Goal

Construct and return the binary tree

Identify the 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.

Construct a Binary Tree

1. Who is the root of the binary tree?
2. A value for left and right children for the root.

Who is the root? What is its left child? What is its right child?

Determine the Scope

• List assumptions
• Define boundaries of the problem

Search the Problem Space

• Look for clues in the problem statement

Classify the Problem

• Decontextualize the Problem

• Can you think of this problem in a different way?

• Can you reframe it?

Problem Representation

• Analyze the Input and Output

• Analyze the Examples

Solve the Problem by Hand

Recognize the Pattern

Identify the Invariants

Brainstorm Solutions

• Brute Force Approach

• Shortcomings

Recursive Approach Base Case: Not an edge case but a way to terminate recursion.

Helper function parameters: inorder,

left half: 0..i-1 (new inorder array) right half: i+1..size-1

Unit of Decomposition is variable in this case.

When the inorder array becomes empty, we terminate recursion.

Write two recursive calls (one for the left and one for the right)

Unit of Work

• Create an instance of TreeNode
• Create the left subtree (subproblem)
• Create the right subtree (subproblem)
• Root must be linked to the left subtree
• Root must be linked to the right subtree

What is the contract between the parent and the child? Output of the subproblems is a binary tree (left and right subtree) We can only get the constructed left and right subtrees after the recursive calls return.

So the links for the left and right must be done after the recursve calls return.

root.left = recur([0..i-1]) root.right = recur([i+1..size-1])

As we go from the leaves to the root. We are mixing declarative and imperative programming in one program.

What should we return from the helper function? We need to return the root object. Counter variable can be used to terminate the recursion.

• Evaluate and Select Approach

Outline the Solution

Key Takeaways

Reflect

• What went right?

• What went wrong?

• What can we improve next time?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {Integer[]} inorder
# @param {Integer[]} postorder
# @return {TreeNode}
def build_tree(inorder, postorder)
  postsize = postorder.size
  if inorder.empty?
      return
  end
   node_val = postorder.last
    node_index = inorder.index(node_val)
    node = TreeNode.new(node_val)
    
    if node_index > 0
        node.left = build_tree(inorder[0..node_index-1], postorder[0..node_index-1])
    end
    if node_index < inorder.size - 1 
        node.right = build_tree(inorder[node_index+1..-1], postorder[node_index...postsize-1])
    end
    
    node
end

inorder = [-,-,-,-,-] postorder = [-,-,-,-,-]

Keep track of number of nodes we have created so far, stop when we have the same number of nodes as the input array.

Where does the root go when we do a post order traversal? Does the root always go to the last position for post order traversal? Yes. How do you decide the left child? We found the root as 3, look in the inorder and search for the root, the number left to the root is the left child.

How do you decide the right child? So for the right child, look in the post order and find the value to the left of the root. This is the right child.

In the inorder, the left value is 15 for 20 so 15 is the left child. In the postorder, the left value of 20 is 7, so 7 is the right child.

How do we know when we need to terminate?

Total number of nodes - number of leaf nodes 5 - 3 = 2 We need to know the number of leaves? How do we identify the leaves from the inorder and postorder arrays.

Return the TreeNode instance for 3.

Problem Definition

Define the Terms

Binary Tree: A tree that has at most two children (left and right child.

Define the Interface

  Input: array of integers, array of integers
  Output: TreeNode instance of binary tree

Identify Implicit Inputs

Define the Goal

Construct and return the binary tree

Identify the 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.

Construct a Binary Tree

1. Who is the root of the binary tree?
2. A value for left and right children for the root.

Who is the root? What is its left child? What is its right child?

Determine the Scope

• List assumptions
• Define boundaries of the problem

Search the Problem Space

• Look for clues in the problem statement

Classify the Problem

• Decontextualize the Problem

• Can you think of this problem in a different way?

• Can you reframe it?

Problem Representation

• Analyze the Input and Output

• Analyze the Examples

Solve the Problem by Hand

Recognize the Pattern

Identify the Invariants

Brainstorm Solutions

• Brute Force Approach

• Shortcomings

Recursive Approach Base Case: Not an edge case but a way to terminate recursion.

Helper function parameters: inorder,

left half: 0..i-1 (new inorder array) right half: i+1..size-1

Unit of Decomposition is variable in this case.

When the inorder array becomes empty, we terminate recursion.

Write two recursive calls (one for the left and one for the right)

Unit of Work

• Create an instance of TreeNode
• Create the left subtree (subproblem)
• Create the right subtree (subproblem)
• Root must be linked to the left subtree
• Root must be linked to the right subtree

What is the contract between the parent and the child? Output of the subproblems is a binary tree (left and right subtree) We can only get the constructed left and right subtrees after the recursive calls return.

So the links for the left and right must be done after the recursve calls return.

root.left = recur([0..i-1]) root.right = recur([i+1..size-1])

As we go from the leaves to the root. We are mixing declarative and imperative programming in one program.

What should we return from the helper function? We need to return the root object. Counter variable can be used to terminate the recursion.

• Evaluate and Select Approach

Analyze Time and Space Complexity

• Time: O( )
• Space: O( )

Outline the Solution

Key Takeaways

Reflect

• What went right?

• What went wrong?

• What can we improve next time?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {Integer[]} inorder
# @param {Integer[]} postorder
# @return {TreeNode}
def build_tree(inorder, postorder)
  postsize = postorder.size
  if inorder.empty?
      return nil
  end
   node_val = postorder.last
    node_index = inorder.index(node_val)
    node = TreeNode.new(node_val)

    if node_index > 0
        node.left = build_tree(inorder[0..node_index-1], postorder[0..node_index-1])
    end

    if node_index < inorder.size - 1 
        node.right = build_tree(inorder[node_index+1..-1], postorder[node_index...postsize-1])
    end

    node
end

inorder = [-,-,-,-,-] postorder = [-,-,-,-,-]

Keep track of number of nodes we have created so far, stop when we have the same number of nodes as the input array.

Where does the root go when we do a post order traversal? Does the root always go to the last position for post order traversal? Yes. How do you decide the left child? We found the root as 3, look in the inorder and search for the root, the number left to the root is the left child.

How do you decide the right child? So for the right child, look in the post order and find the value to the left of the root. This is the right child.

In the inorder, the left value is 15 for 20 so 15 is the left child. In the postorder, the left value of 20 is 7, so 7 is the right child.

How do we know when we need to terminate?

Total number of nodes - number of leaf nodes 5 - 3 = 2 We need to know the number of leaves? How do we identify the leaves from the inorder and postorder arrays.

Return the TreeNode instance for 3.

Problem Definition

Define the Terms

Binary Tree: A tree that has at most two children (left and right child.

Define the Interface

  Input: array of integers, array of integers
  Output: TreeNode instance of binary tree

Identify Implicit Inputs

Define the Goal

Construct and return the binary tree

Identify the 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.

Construct a Binary Tree

1. Who is the root of the binary tree?
2. A value for left and right children for the root.

Who is the root? What is its left child? What is its right child?

Determine the Scope

• List assumptions
• Define boundaries of the problem

Search the Problem Space

• Look for clues in the problem statement

Classify the Problem

• Decontextualize the Problem

• Can you think of this problem in a different way?

• Can you reframe it?

Problem Representation

• Analyze the Input and Output

• Analyze the Examples

Solve the Problem by Hand

Recognize the Pattern

Identify the Invariants

Brainstorm Solutions

• Brute Force Approach

• Shortcomings

Recursive Approach Base Case: Not an edge case but a way to terminate recursion.

Helper function parameters: inorder,

left half: 0..i-1 (new inorder array) right half: i+1..size-1

Unit of Decomposition is variable in this case.

When the inorder array becomes empty, we terminate recursion.

Write two recursive calls (one for the left and one for the right)

Unit of Work

• Create an instance of TreeNode
• Create the left subtree (subproblem)
• Create the right subtree (subproblem)
• Root must be linked to the left subtree
• Root must be linked to the right subtree

What is the contract between the parent and the child? Output of the subproblems is a binary tree (left and right subtree) We can only get the constructed left and right subtrees after the recursive calls return.

So the links for the left and right must be done after the recursve calls return.

root.left = recur([0..i-1]) root.right = recur([i+1..size-1])

As we go from the leaves to the root. We are mixing declarative and imperative programming in one program.

What should we return from the helper function? We need to return the root object. Counter variable can be used to terminate the recursion.

• Evaluate and Select Approach

Analyze Time and Space Complexity

• Time: O( )
• Space: O( )

Outline the Solution

Key Takeaways

Reflect

• What went right?

• What went wrong?

• What can we improve next time?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {Integer[]} inorder
# @param {Integer[]} postorder
# @return {TreeNode}
def build_tree(inorder, postorder)
  postsize = postorder.size
  if inorder.empty?
      return
  end
   node_val = postorder.last
    node_index = inorder.index(node_val)
    node = TreeNode.new(node_val)

    if node_index > 0
        node.left = build_tree(inorder[0..node_index-1], postorder[0..node_index-1])
    end

    if node_index < inorder.size - 1 
        node.right = build_tree(inorder[node_index+1..-1], postorder[node_index...postsize-1])
    end

    node
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {Integer[]} inorder
# @param {Integer[]} postorder
# @return {TreeNode}
def build_tree(inorder, postorder)
    if inorder.none?
        return
    end

    node = TreeNode.new(postorder.last)
    i = inorder.index(postorder.last)

    node.left = build_tree(inorder[0...i], postorder[0...i])
    node.right = build_tree(inorder[i+1..-1], postorder[i...-1])

    node
end