Introduction to Trees

When learning data structures, trees mark a turning point. They move us beyond linear structures like arrays and linked lists, into the world of hierarchical data — a structure where relationships matter as much as values.

Why Trees Matter in Computer Science

Trees appear everywhere in computing:

• Hierarchical Data Representation

  • File systems (folders containing files and subfolders).
  • XML/HTML documents (DOM tree).
  • Organization charts.

• Databases

  • B-trees and B+ trees form the backbone of most relational database indexes.
  • Binary search trees (BSTs) for efficient searching.

• Compilers & Parsing

  • Abstract Syntax Trees (ASTs) represent the structure of source code.

• Artificial Intelligence

  • Decision trees and game trees power algorithms for planning and search.

• Networking & Operating Systems

  • Routing tables, memory allocation trees, process hierarchies.

In short, trees help us represent data with parent-child relationships efficiently.

Where You’ll Encounter Trees

If you’re preparing for technical interviews or doing competitive programming, trees are unavoidable. Expect to see them in:

• LeetCode / Codeforces / HackerRank problems.
• Google, Meta, Amazon interviews (common focus on tree traversals, Lowest Common Ancestor, diameter, etc.).
• Competitive contests requiring efficient data queries (segment trees, Fenwick trees).

Mastering trees builds intuition that directly transfers to graph algorithms, since a tree is just a special type of graph.

A Quick Mental Model

Here’s a simple way to think about trees in the broader landscape of data structures:

• Linked List → A linear chain of nodes (like a train).
• Tree → A branching structure of nodes (like a family tree).
• Graph → A general network of nodes and edges (like a city map).

Basic Terminology in Trees

Before diving into traversals or algorithms, it’s important to understand the core terminology of trees. These definitions will appear again and again, both in theory and in interview problems.

Node

A node is the basic building block of a tree.

• Each node typically stores a value (or data).
• It may also have pointers (or references) to its children.

Example in code (binary tree node in TypeScript):

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

Root

• The root is the topmost node in a tree.

• It has no parent.

• Every other node is a descendant of the root.

Parent, Child, and Sibling

• Parent → is a node with one or more child nodes.

• Child → is a node that descends from a parent.

• Siblings → are nodes that share the same parent.

Leaf

          A         <- Root
        /   \
       B     C     <- B and C are children of A (A is their parent)
      / \     \
     D   E     F <- D, E, F are leaf nodes (no children)

• A leaf is a node that has no children.

• Also called a terminal node.

Height, Depth, and Level

These terms are often confused, so let’s clarify:

• Depth of a node → Distance from the root to that node (root has depth 0).

• Height of a node → Longest path from that node to a leaf.

• Height of Tree → Height of the root node.

• Level of a node → Depth + 1 (so the root is at level 1).

        A (root)
       / \
      B   C
     / \
    D   E

Depth of A = 0

Depth of B = 1

Height of B = 1 (longest path to D or E)

Height of A = 2

Level of C = 2

Subtree

• A subtree is simply a tree within a tree.

• Every node defines the root of its own subtree.

For example, in the above diagram, the node B and its children (D, E) form a subtree.

Types of Trees

Trees can take many forms depending on how many children nodes each node has and how balanced the tree is. Understanding the different types of trees helps in choosing the right data structure for a problem.

General Tree

A general tree is a tree where a node can have any number of children.

        A
      / | \
     B  C  D
       / \
      E   F

• Node A has three children: B, C, and D.

• Node C has two children: E and F.

• There is no restriction on the number of children per node.

Binary Tree

A binary tree is a tree where each node has at most 2 children, commonly referred to as left and right.

        A
       / \
      B   C
     / \
    D   E

• Node A has two children: B and C.

• Node B has two children: D and E.

• Node C has no children.

Full / Complete / Perfect Binary Trees

Full Binary Tree

• Every node has 0 or 2 children.

        A
       / \
      B   C
     / \
    D   E

• C is a leaf, B has 2 children → satisfies full binary tree properties.

Complete Binary Tree

• All levels are completely filled except possibly the last, which is filled from left to right.

        A
       / \
      B   C
     / \  /
    D   E F

• Level 3 is partially filled, but nodes are filled left to right → complete binary tree.

Perfect Binary Tree

• All internal nodes have 2 children and all leaves are at the same level.

        A
       / \
      B   C
     / \ / \
    D  E F  G

• Fully balanced, no missing nodes → perfect binary tree.

Skewed Tree

A skewed tree is a tree where all nodes have only one child.

• Left-skewed: each node has only a left child.

Left-Skewed
    A
   /
  B
 /
C

• Right-skewed: each node has only a right child.

Right-Skewed
A
 \
  B
   \
    C

• Skewed trees behave like linked lists.
• Traversals have worst-case time complexity of O(n).