GraphLab

Graph theory & algorithm visualizer
About Binary tree from traversals

GraphLab › Binary tree from traversals

Construct a Binary Tree from Pre-order and In-order Traversal

A binary tree can be rebuilt from two of its traversals, as long as one of them is the in-order sequence.

Pre-order + in-order

  1. The first value of the pre-order sequence is the root.
  2. Find the root in the in-order sequence. Everything to its left forms the left subtree, everything to its right the right subtree.
  3. Repeat for each subtree with the matching part of both sequences.

With post-order + in-order it works the same way, but the root is the last value of the post-order sequence.

Binary search tree

Insert values one by one: each value goes left if it is smaller than the current node and right if it is larger, until it finds an empty place.

Try it in GraphLab

Type the sequences, press Build and step through the construction. Then use Traverse to check the orders of the finished tree.

More topics