Binary tree and BST tool

The tree

Traversals

Preorder (root, left, right)

MANGO BANANA APPLE PEAR ORANGE

Inorder (left, root, right)

APPLE BANANA MANGO ORANGE PEAR

Postorder (left, right, root)

APPLE BANANA ORANGE PEAR MANGO

Level order

MANGO BANANA PEAR APPLE ORANGE

About the tree

Root

MANGO

Number of nodes (size)

5

Height = depth (edges from the root to the deepest leaf)

2

Levels (the root is at level 0)

3

Leaves (external nodes)

APPLE, ORANGE

Internal nodes (not the root)

BANANA, PEAR

Full binary tree (every node has 0 or 2 children)

No

Complete binary tree

No

Binary search tree (inorder is in order)

Yes

Inserting, one value at a time

Each value starts at the root and goes left if smaller, right if larger, until there is a free place.

1. MANGO: the first value is the root
2. BANANA: BANANA < MANGO: go left → left of MANGO
3. PEAR: PEAR > MANGO: go right → right of MANGO
4. APPLE: APPLE < MANGO: go left; APPLE < BANANA: go left → left of BANANA
5. ORANGE: ORANGE > MANGO: go right; ORANGE < PEAR: go left → left of PEAR