DSA Trees

A tree is a hierarchical data structure made of nodes connected by edges, starting from a single root and branching outward to represent parent-child relationships.

What Is a Tree?

Unlike a list or array, where every element sits in a single line, a tree organizes data hierarchically. Each tree has one root node at the top, and every other node is reached by following a path of edges down through parent-child relationships - the same shape used by file systems, org charts, and a web page's DOM.

Core Tree Terminology

  • Root - the single node at the top of the tree with no parent
  • Node - any element in the tree; it stores a value and references to its children
  • Edge - the connection between a parent node and a child node
  • Parent / Child - a node directly above another is its parent; the node below is its child
  • Leaf - a node with no children
  • Subtree - a node together with all of its descendants, which is itself a valid tree

Example

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child_node):
        self.children.append(child_node)

# Build a small company org chart
ceo = TreeNode('CEO')
cto = TreeNode('CTO')
cfo = TreeNode('CFO')
ceo.add_child(cto)
ceo.add_child(cfo)
cto.add_child(TreeNode('Engineering Manager'))

print(ceo.value)                       # CEO
print([child.value for child in ceo.children])  # ['CTO', 'CFO']

Height, Depth, and Traversal

The depth of a node is the number of edges from the root down to that node; the root itself has depth 0. The height of a tree is the number of edges on the longest path from the root down to a leaf. To actually process every value in a tree, you traverse it - visiting nodes in a defined order such as depth-first (going as deep as possible before backtracking) or breadth-first (visiting every node level by level).

TraversalOrderTypical Use
Preorderroot, then left, then rightCopying or serializing a tree
Inorderleft, then root, then rightReading values in sorted order (binary search trees)
Postorderleft, then right, then rootDeleting a tree or computing sizes bottom-up
Level-order (BFS)one level at a time, top to bottomFinding the shortest path or nearest node

Example

def tree_height(node):
    if not node.children:
        return 0
    return 1 + max(tree_height(child) for child in node.children)

print(tree_height(ceo))   # 2  (CEO -> CTO -> Engineering Manager)

Example

def preorder(node, depth=0):
    print('  ' * depth + node.value)
    for child in node.children:
        preorder(child, depth + 1)

preorder(ceo)
# CEO
#   CTO
#     Engineering Manager
#   CFO
Note: Recursion is a natural fit for tree algorithms because every subtree is itself a smaller tree - most traversal, search, and height functions can be written in just a few lines by calling themselves on each child.
Note: Recursive tree functions have no built-in depth limit in Python beyond the interpreter's recursion limit (1000 by default). Extremely deep or unbalanced trees can raise a RecursionError - an iterative traversal using an explicit stack avoids this.

Exercise: DSA Trees

What is the "root" of a tree?

Keep Going

Data Structures Interview QuestionsPractice real questions asked for Data StructuresSoftware Engineer SalarySee what Software Engineer roles pay in the marketAuto Apply for JobsApply to open roles related to Data Structures and tweak your resume