Core Concept Mastery • DSA Module
Tree terminology provides precise language to describe relationships and properties of nodes in a tree. Key terms include Root, Leaf, Parent, Child, Sibling, Height, Depth, Level, and Degree.
Think of a company org chart. The CEO is the Root. Managers reporting to the CEO are at Level 1. Employees reporting to managers are at Level 2. An employee with no direct reports is a Leaf. Two employees reporting to the same manager are Siblings. The number of levels from CEO to the deepest employee is the Height.
Click the buttons to identify parts of the tree!
Select a term to visualize.
Longest path from node to leaf. Measured downward.
Height of Root = Height of Tree
Distance from Root to node. Measured upward.
Depth of Root = 0
All nodes at same depth. Root is Level 0.
Number of children a node has.
The Language of Trees
Essential Terms
Root: The topmost node with no parent. Every tree has exactly one root. Like the CEO of a company or the main folder in a directory.
Node: Any element in the tree that contains data. Can be Root, internal node, or Leaf.
Parent: A node that has children. The node directly above another node in the hierarchy.
Child: A node directly below a parent. A node can have zero, one, or multiple children.
Sibling: Nodes that share the same parent. Like brothers and sisters in a family tree.
Leaf (External Node): A node with no children. The endpoints of branches. In a file system, files are leaves; folders are internal nodes.
Internal Node: A node that has at least one child. Not a leaf.
Edge: The connection between a parent and child node. Represents the relationship.
Path: A sequence of nodes connected by edges. From Root to any node, there's exactly one path.
Ancestor: Any node on the path from Root to a given node (including the node itself).
Descendant: Any node in the subtree rooted at a given node (including the node itself).
Height of a Node: The longest path from that node to a leaf. Height of a leaf is 0.
Height of a Tree: The height of the Root node. The longest path from Root to any leaf.
Depth of a Node: The number of edges from Root to that node. Depth of Root is 0.
Level: All nodes at the same depth. Root is at Level 0, its children at Level 1, etc.
Degree of a Node: The number of children that node has.
Degree of a Tree: The maximum degree of any node in the tree.
Subtree: Any node and all its descendants form a subtree. Every node is the root of its own subtree.
Why Height vs Depth?
Understanding tree terminology is essential for communicating about tree algorithms, analyzing complexity, and implementing tree operations. Without precise terminology, you can't discuss tree properties like 'the height of the left subtree' or 'nodes at depth 3'.
"What is the difference between height and depth of a node?"
Height is measured downward from a node (the longest path from that node to a leaf). Depth is measured upward from the Root (the number of edges from Root to that node). For the Root, height equals the tree height and depth is 0. For a leaf, height is 0 and depth equals the tree height.