Given the following traversal sequences of a binary tree: Postorder: 4, 3, 5, 1, 7, 6, 2 Reference Order: 4, 3, 1, 5, 2, 7, 6 Construct the binary…

“Reference Order” here behaves as the inorder sequence (it is consistent with the postorder only that way). Rule: the last postorder value is the root; split the inorder around it; repeat on each side.

• Postorder ends with 2 → root 2. Inorder: left {4, 3, 1, 5}, right {7, 6}.
• Left part, postorder 4 3 5 1 → root 1. Inorder: left {4, 3}, right {5}.
• {4, 3}: postorder 4 3 → root 3; inorder 4 3 → 4 is the left child of 3.
• Right part, postorder 7 6 → root 6; inorder 7 6 → 7 is the left child of 6.

        2
       / \
      1   6
     / \  /
    3   5 7
   /
  4

Check: postorder 4 3 5 1 7 6 2 ✓, inorder 4 3 1 5 2 7 6 ✓.

— rhs