Basic Tree Terminologies
Idea Like You Are 10
Think of a tree like a family chart.
One person is at the top, and others grow below.
Main Terms
Node
An item in the tree.
Root
The topmost node.
Edge
The connection between two nodes.
Parent
A node directly above another node.
Child
A node directly below another node.
Siblings
Nodes with the same parent.
Leaf Node
A node with no children.
Internal Node
A node with at least one child.
Degree Of Node
The number of children of a node.
Degree Of Tree
The maximum degree of any node in the tree.
Level
How far a node is from the root.
Depth
Number of edges from root to the node.
Height Of Node
Number of edges in the longest path from that node down to a leaf.
Height Of Tree
Height of the root.
Subtree
A smaller tree inside the tree.
Ancestor
A node above another node.
Descendant
A node below another node.
Important Binary Tree Formulas
Maximum nodes at level l
2^l
Maximum nodes in a binary tree of height h
2^(h+1) - 1
Minimum height for n nodes in a balanced binary tree
About log2(n)
Why Trees Are Useful
- organize hierarchical data
- fast searching in good tree types
- used in file systems, databases, compilers, and AI