Construct Binary Tree from Inorder and Preorder

Root pick from preorder + inorder range partitioning

Read Here
Step0/26
Created0
Preorder Ptr0
Back To Trees List

Python Code

7            nonlocal pre_ptr
8            if left > right:
9                return None
10 
●            root_val = preorder[pre_ptr]
12            pre_ptr += 1
......
15 
16            root.left = build(left, mid - 1)
17            root.right = build(mid + 1, right)
18            return root
19
Current Line (11): Pick root from preorder

Tree Structure

3791520
Operation:Pick Root

Build Progress

Pre Ptr

0

Inorder Pivot

-

Traversal Inputs

Preorder: [3, 9, 20, 15, 7]

Inorder: [9, 3, 15, 20, 7]

Range: [0..-1]

Created Order

Created nodes appear here...
Step 1: Pick Root

Build Stack

Stack is empty. Click Next to begin!

Step Explanation

Line 11: pick_root

Pick 3 from preorder and split inorder at index 1

  • > Meaning: Current preorder pointer always gives the subtree root.
  • > Why: Preorder order is Root, Left, Right.
  • > Next: Advance pointer and create this node.
  • > Progress snapshot: 0/26 steps, 0 nodes created.
Unvisited
Left
Current
Right
Done