Data Structure and Algorithms – Trees

Data Structures: Tree Basics

A tree is a non-linear hierarchical data structure consisting of nodes connected by edges. Hover over nodes to see their terminology.

Root
- Internal
  - Leaf
  - Leaf
- Leaf

Hover over a node to see terminology…

N-ary Trees

A tree where a node can have at most N children. This example shows a 4-ary tree.

A
- B
- C
  - G
- D
- E

Binary Trees

A tree where each node has at most two children, referred to as the left child and the right child.

Root
- Left Child
  - Left
  - Right
- Right Child
  - Left

Tree Traversals

Watch how different algorithms visit nodes in a Binary Tree.

1
- 2
  - 4
  - 5
- 3

Output:

Expression Trees

A specific kind of binary tree used to evaluate expressions. Leaves are operands and internal nodes are operators. Hover over nodes to see the sub-expression they represent.

*
- +
  - A
  - B
- C

Hover over a node to see its sub-expression…

References

C. to, “class of algorithms,” Wikipedia.org, Apr. 15, 2004. https://en.wikipedia.org/wiki/Tree_traversal.
Bruno R. Preiss, Data structures and algorithms with object-oriented design patterns in C++. John Wiley & Sons, Inc., 605 Third Ave. New York, NY, United States, August 1998.