Tree

Think about your computer’s folders. A folder can have files and other folders inside it, and those folders can have even more folders inside them. That branching, “one thing leads to many things” shape is exactly what a tree looks like in programming. It is one of the most important shapes data can take, and this guide walks you through everything you need to know, from the basics all the way to a fun bit of math that ties it all together.

What Even Is a Tree?

A tree is a way of organizing data that branches out, kind of like a real tree, except it usually gets drawn upside down with the root at the top.

You have probably used trees without even realizing it:

• Your computer’s file system (folders inside folders)
• A company’s organization chart (CEO at the top, teams branching below)
• The HTML structure of a webpage (a page containing sections, containing paragraphs, containing text)
• Database indexes, which use a special kind of tree to find data fast

Tip

Unlike a list where everything is in one straight line, a tree lets one item have many “children” coming off it. That branching is what makes it a tree instead of just a list.

Getting Comfortable With Tree Vocabulary

Before going further, let us learn the words people use when talking about trees. Here is a small tree to look at:

        A
       / \
      B   C
     / \   \
    D   E   F

• Root - the very top node, the starting point. Here, that is A.
• Parent - a node that has something branching below it. A is the parent of B and C.
• Children - the nodes branching off a parent. B and C are children of A.
• Leaf nodes - nodes with no children at all, the “end of the line.” Here, those are D, E, and F.
• Height - the longest path you can take from the root down to a leaf.
• Depth - how far down a particular node sits, counting from the root.
• Subtree - any node, along with everything branching below it, counts as its own smaller tree.

Binary Trees and Their Different Shapes

A binary tree is simply a tree where every node has at most two children, usually called the left child and the right child. Binary trees come in a few recognizable shapes, and knowing their names helps a lot when reading about data structures.

Full Binary Tree

A tree is called “full” when every single node has either zero children or exactly two children. Nobody is allowed to have just one child.

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

This one is a valid full binary tree, since every node has 0 or 2 children.

This one is not valid:

    A
   /
  B

B has only one child slot used and one missing, so this breaks the “full” rule.

A neat little fact about full binary trees: if you count the number of nodes that have children (internal nodes), the total number of nodes always works out to 2 times internal_nodes + 1. Full binary trees show up a lot in things like expression trees (the kind used to represent math expressions like (2 + 3) * 4).

Complete Binary Tree

A tree is called “complete” when every level is totally full, except possibly the very last level, and on that last level, nodes are filled in strictly left to right with no gaps.

        A
       / \
      B   C
     / \  /
    D  E F

This matters a lot in practice because heaps (a structure used for priority queues) are built on exactly this shape. The nice thing about complete binary trees is that you can store them directly inside a plain array with no wasted space, and that gives really good performance because arrays are friendly to your computer’s memory cache.

Note

You might also hear the term “almost complete binary tree.” In most computer science material, this means the exact same thing as a complete binary tree: every level filled except the last, and the last level filled from left to right.

Visiting Every Node - Tree Traversals

Traversal just means visiting every node in the tree exactly once, in some specific order. There are three classic ways to do this, and they only differ in when you “visit” (read or print) the current node compared to its children.

Inorder Traversal (Left, then Root, then Right)

        A
       / \
      B   C
     / \
    D   E

Order you would visit: D, B, E, A, C

def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

The reason this one is special: if you run inorder traversal on a binary search tree, you get all the values back out in perfectly sorted order. We will come back to this a bit later.

Preorder Traversal (Root, then Left, then Right)

Using the same tree, the order becomes: A, B, D, E, C

def preorder(node):
    if not node:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

This is handy when you want to copy a tree or save it to a file (serialize it), because visiting the root first means you always know where each subtree starts.

Postorder Traversal (Left, then Right, then Root)

Order: D, E, B, C, A

def postorder(node):
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

This order is great for deleting a tree safely, since you clean up all the children before removing the parent, so you never lose your reference to a node you still need to delete.

Tip

A simple way to remember all three: just notice where “Root” sits in the name. Preorder visits root first. Inorder visits root in the middle. Postorder visits root last.

Rebuilding a Tree From Its Traversals

Here is a fun puzzle: if someone gives you the traversal results, can you figure out the exact original tree? It turns out the answer depends entirely on which traversals you have.

Preorder + Inorder Makes a Unique Tree

This combination always works because of one simple fact: preorder tells you the root first, and inorder tells you everything to the left of the root and everything to the right of the root.

Let us walk through an example.

Preorder: A B D E C F
Inorder:  D B E A C F

1. Find the root. The first value in preorder is always the root, so the root here is A.

2. Split the inorder list around the root. Find A in the inorder list. Everything before it is the left subtree, everything after it is the right subtree.

   Left inorder  = D B E
   Right inorder = C F

3. Repeat the same process on each half, treating them as their own smaller trees, until there is nothing left to split.

Here is the code that does exactly this:

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None

    root_val = preorder[0]
    root = TreeNode(root_val)

    i = inorder.index(root_val)

    root.left = buildTree(preorder[1:i+1], inorder[:i])
    root.right = buildTree(preorder[i+1:], inorder[i+1:])

    return root

Postorder + Inorder Also Works

Same idea, just flipped. This time, the root is the last value in postorder instead of the first.

def buildTree(postorder, inorder):
    if not postorder or not inorder:
        return None

    root_val = postorder[-1]
    root = TreeNode(root_val)

    i = inorder.index(root_val)

    root.left = buildTree(postorder[:i], inorder[:i])
    root.right = buildTree(postorder[i:-1], inorder[i+1:])

    return root

Why Preorder + Postorder Is Not Enough

This one trips people up, so let us slow down. Preorder tells you the order “root, left, right.” Postorder tells you “left, right, root.” Notice that neither one tells you where the left subtree ends and the right subtree begins. Without that boundary, more than one tree shape can produce the exact same preorder and postorder output.

Take this small example:

Preorder:  A B C
Postorder: C B A

All three of these trees give you that exact same preorder and postorder:

Tree 1:        Tree 2:        Tree 3:
    A              A              A
   /                \            /
  B                  B          B
 /                    \          \
C                      C          C

So just having preorder and postorder leaves you guessing.

Caution

There is one special exception: if you are told the tree is a full binary tree (every node has 0 or 2 children, remember?), then preorder + postorder is enough to rebuild it uniquely. Because every branching point is forced to have exactly two children or none, there is no ambiguity left.

Speeding Up Tree Construction

If you write the rebuilding code exactly as shown above, it actually runs in O(n squared) time, because every step searches through the inorder list with .index(), and that search itself takes time.

There is a neat trick to fix this: build a hashmap once at the very start that instantly tells you the position of any value in the inorder list. That turns every lookup into an instant O(1) operation, bringing the whole thing down to O(n).

def build(preorder, inorder):
    index = {v: i for i, v in enumerate(inorder)}
    pre_i = 0

    def helper(left, right):
        nonlocal pre_i
        if left > right:
            return None

        root_val = preorder[pre_i]
        pre_i += 1
        root = TreeNode(root_val)

        mid = index[root_val]

        root.left = helper(left, mid - 1)
        root.right = helper(mid + 1, right)
        return root

    return helper(0, len(inorder) - 1)

This little optimization is something interviewers love to see, since it shows you understand why the slow version is slow, not just that a faster version exists.

How Fast Are Trees, Really?

For traversals (just visiting every node once):

• Time: O(n), since you touch each node exactly once
• Space: O(h), where h is the height of the tree, because that is how deep your recursive calls go

For building a tree from traversals:

• Naive version: O(n squared)
• With the hashmap trick: O(n)

Binary Search Trees - Trees That Stay Organized

Now that you know what a regular tree looks like, let us meet a special, very useful version of it: the Binary Search Tree, or BST for short.

A BST follows one golden rule at every single node:

Everything in the left subtree < this node's value < everything in the right subtree

Let us insert the values 50, 30, 70, 20, 40, 60, 80 one at a time and see what we get:

           50
         /    \
       30      70
      /  \    /  \
    20   40  60   80

Notice how anything smaller than a node always lives somewhere in its left branch, and anything bigger always lives somewhere in its right branch. That single rule is what makes a BST so useful.

Tip

Think of a BST like a well organized bookshelf where every book to the left of a marker is “smaller” and everything to the right is “bigger.” Whenever you are looking for a book, you instantly know which half to check, so you never waste time looking through the wrong side.

Why Bother With a BST?

A BST gives you fast searching, fast inserting, and fast deleting, kind of like binary search, except it works as a living, changeable structure instead of a fixed sorted list. This is why BSTs show up everywhere: databases, file systems, compilers, and a huge chunk of coding interview questions.

How Fast Is a BST?

Operation	Average Case	Worst Case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

That worst case shows up when the tree becomes “skewed,” meaning it basically turns into a straight line instead of branching out evenly:

10
  \
   20
     \
      30
        \
         40

This looks and behaves exactly like a linked list, which means every operation slows down to O(n). Balanced BSTs avoid this problem, but that is a topic for another day.

Building a BST Node

Every node just needs to hold a value and point to its left and right children:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

Inserting a Value

The logic is simple: if the tree is empty, the new value becomes the root. Otherwise, compare the new value against the current node. Go left if it is smaller, go right if it is bigger, and keep going until you find an empty spot.

function insert(root, value):
    if root is NULL:
        return new Node(value)

    if value < root.data:
        root.left = insert(root.left, value)
    else if value > root.data:
        root.right = insert(root.right, value)

    return root

Here is what inserting 25 looks like, step by step:

Before:           After inserting 25:
    30                  30
   /                   /
 20                  20
                       \
                        25

And the actual Python code:

def insert(root, data):
    if root is None:
        return Node(data)

    if data < root.data:
        root.left = insert(root.left, data)
    elif data > root.data:
        root.right = insert(root.right, data)

    return root

Searching for a Value

Searching follows the exact same comparison logic as inserting. Compare, then decide which direction to go.

function search(root, value):
    if root is NULL:
        return False

    if root.data == value:
        return True

    if value < root.data:
        return search(root.left, value)
    else:
        return search(root.right, value)

Searching for 60 in our earlier tree would look like this:

        50
          \
           70
          /
        60   <- found it

def search(root, data):
    if root is None:
        return False

    if root.data == data:
        return True
    elif data < root.data:
        return search(root.left, data)
    else:
        return search(root.right, data)

Getting Sorted Output for Free

Remember inorder traversal from earlier? Run it on a BST, and you automatically get every value back in perfectly sorted order, with zero extra sorting work needed.

Inorder result: 20, 30, 40, 50, 60, 70, 80

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

Deleting a Value (The Trickiest Part)

Deleting from a BST has three different situations to handle, depending on how many children the node you are deleting has.

Case 1: The node has no children (it is a leaf)

Just remove it. Nothing else to do.

   50
     \
      70   <- delete this, it has no children

Case 2: The node has exactly one child

Just connect the node’s parent directly to that one child, skipping over the deleted node.

   50
     \
      70
        \
         80

Case 3: The node has two children

This is the tricky one. Here is the trick that makes it work:

1. Find the inorder successor - this just means the smallest value in the node’s right subtree. You find it by going as far left as possible inside that right subtree.

2. Copy that successor’s value into the node you wanted to delete.

3. Now delete the successor itself from its original spot. Since the successor is guaranteed to have at most one child, this step always falls back into Case 1 or Case 2.

      50
     /  \
   30    70
        /  \
      60   80

Finding the minimum value is straightforward, just keep walking left:

   70
  /
60  <- this is the minimum, walk left until you hit None

def find_min(root):
    while root.left:
        root = root.left
    return root.data


def delete(root, data):
    if root is None:
        return root

    if data < root.data:
        root.left = delete(root.left, data)
    elif data > root.data:
        root.right = delete(root.right, data)
    else:
        # zero or one child
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left

        # two children
        successor = find_min(root.right)
        root.data = successor
        root.right = delete(root.right, successor)

    return root

Caution

A very common bug: forgetting to actually save the result back. Calling delete(root, value) does nothing on its own unless you assign it back, like this:

self.head = delete(self.head, value)

Without that reassignment, the deletion happens inside the function but never gets reflected in your actual tree.

A Simple Way to Picture a BST

Think of a BST like a paper dictionary. Words that come earlier alphabetically live toward the front (left), words that come later live toward the back (right), and that ordering is exactly what lets you flip straight to roughly the right page instead of reading from page one every time.

How Does a BST Compare to Other Structures?

Structure	Search Speed
Array	O(n)
BST (average)	O(log n)
HashMap	O(1)
Linked List	O(n)

A BST trades away the blazing O(1) speed of a hashmap, but in exchange, it keeps everything in sorted order, which a hashmap cannot do. That trade-off is exactly why both structures exist side by side.

Mistakes Beginners Often Make With BSTs

• Forgetting to return the root at the end of insert or delete. Since these are recursive functions rebuilding pointers as they go, skipping the return breaks the chain.
• Not handling all three delete cases. It is tempting to only handle the easy leaf case and forget about one-child or two-children nodes.
• Forgetting to reassign the root variable after calling delete, as shown in the warning above.
• Mixing up successor and predecessor. The successor is the next bigger value (smallest in the right subtree); the predecessor is the next smaller value (biggest in the left subtree).
• Ignoring the worst case. A BST built from already-sorted input data turns into a skewed, slow, linked-list-like shape.

Good Questions to Practice With BSTs

If you are prepping for interviews, these are the classic problems worth trying:

• Validate whether a given tree is actually a correct BST
• Find the lowest common ancestor of two nodes
• Find the kth smallest value in a BST
• Sum all values within a given range
• Convert a BST into a sorted array
• Calculate the height of a BST
• Tell the difference between a balanced and an unbalanced BST
• Find the successor and predecessor of a given node

A Fun Question: How Many Different BSTs Are Possible?

Here is an interesting question that connects trees to a surprising bit of math: if you have n distinct values, how many different BST shapes can you build using exactly those values?

It turns out there is a clean, famous formula for this, built around something called Catalan numbers.

n  :  0   1   2   3    4
C  :  1   1   2   5   14

So with 2 values you get 2 possible BSTs, with 3 values you get 5 possible BSTs, and with 4 values you get 14 possible BSTs.

Seeing It With n = 2

Say your values are {1, 2}. There are exactly 2 valid BST shapes:

1            2
 \          /
  2        1

That matches C(2) = 2.

Seeing It With n = 3

With values {1, 2, 3}, there are exactly 5 valid shapes:

1        1        2        3        3
 \        \      / \      /        /
  2        3    1   3    2        1
   \      /                \        \
    3    2                  1        2

That matches C(3) = 5.

The Big Idea: Picking a Root

Here is the core insight that explains where this formula comes from. For any group of values, picking any one value as the root automatically decides everything else:

• Every value smaller than the root must go into the left subtree
• Every value bigger than the root must go into the right subtree

So if you pick the i-th smallest value as your root out of n total values:

Left subtree gets  (i - 1) values
Right subtree gets (n - i) values

And here is the neat part: the left subtree and right subtree are built completely independently of each other. Whatever shape the left subtree takes does not affect what shapes are possible for the right subtree. Whenever two choices are independent like this, you multiply their possibilities together.

Number of BSTs with root i = (BST shapes possible on the left) times (BST shapes possible on the right)

Building the Full Formula

Since the root could be any of the n values, you need to add up the result for every possible choice of root:

C(n) = sum of [ C(i - 1) * C(n - i) ]   for i = 1 up to n

And we need one starting point to make the whole thing work:

C(0) = 1

Note

Why does an empty tree count as 1 shape? Because “having nothing” is still a single, valid, well defined possibility. If a node’s left subtree is empty, that empty space is not “zero options,” it is “exactly one option: nothing goes there.”

Writing the Recursive Version

This formula translates almost word for word into code:

def catalan(n):
    if n == 0 or n == 1:
        return 1

    result = 0
    for i in range(1, n + 1):
        result += catalan(i - 1) * catalan(n - i)

    return result


print(catalan(3))  # Output: 5

Walking Through n = 4 With a Specific Root

Say n = 4, with values 1, 2, 3, 4, and we choose 2 as the root.

Left subtree  = {1}      -> 1 value
Right subtree = {3, 4}   -> 2 values

Number of BSTs possible with 2 as root:

C(1) * C(2) = 1 * 2 = 2

You would repeat this same calculation for every possible root from 1 to 4, then add all those results together to get the final C(4) = 14.

A Faster Way: The Direct Math Formula

The recursive version above is great for understanding why the formula works, but it is painfully slow for large n because it recalculates the same smaller values over and over again. Luckily, there is also a direct mathematical shortcut:

C(n) = (2n)! / ((n + 1)! * n!)

import math

def catalan_math(n):
    return math.factorial(2 * n) // (math.factorial(n + 1) * math.factorial(n))

print(catalan_math(4))  # Output: 14

Caution

The plain recursive version runs in exponential time, which is genuinely very slow for bigger values of n. In interviews, it is usually fine (and expected) to first explain the recurrence relation to show you understand why it works, and then mention that it can be sped up using the direct formula or dynamic programming.

Catalan Numbers Show Up in Other Places Too

Counting BST shapes is far from the only place this sequence appears. The exact same numbers also count:

• The number of ways to arrange valid, balanced parentheses
• The number of full binary trees with a given number of leaves
• Certain types of stack-based permutations
• The number of ways to slice a polygon into triangles
• Counting paths that look like mountain ranges, going up and down without crossing a baseline

Mistakes to Avoid With Catalan Numbers

A very common wrong guess is assuming Catalan numbers follow the same pattern as Fibonacci:

C(n) = C(n - 1) + C(n - 2)     This is WRONG

The actual, correct relationship is:

C(n) = sum of [ C(i - 1) * C(n - i) ]   for i = 1 to n

Other things people often get wrong:

• Forgetting that C(0) = 1 is the base case that makes everything else work
• Thinking the actual values in the BST matter, when really only the shape matters (any 3 distinct values produce the same 5 possible shapes)
• Mixing up “number of shapes” with “number of orderings” (permutations), which is a different kind of counting problem entirely

Quick Reference

Tree

A branching structure where each node can have children. The root sits at the top, leaves sit at the bottom with no children.

Traversal

A way of visiting every node exactly once. Inorder, preorder, and postorder differ only in when the current node gets visited.

Rebuilding a Tree

Preorder + inorder, or postorder + inorder, always rebuild a unique tree. Preorder + postorder alone is ambiguous unless the tree is full.

Binary Search Tree

A binary tree where left children are always smaller and right children are always bigger than their parent. Gives fast search, insert, and delete.

BST Delete

Three cases: no children (just remove), one child (skip over it), two children (swap with the inorder successor, then delete the successor).

Catalan Numbers

Counts how many different BST shapes are possible for n distinct values. Built by picking each possible root and multiplying left and right possibilities.

Summary

The Core Idea

• A tree branches out from a root into children, all the way down to leaf nodes with nothing below them
• Inorder, preorder, and postorder traversals differ only in when the current node gets visited
• A binary search tree keeps smaller values to the left and bigger values to the right, which makes search, insert, and delete all fast
• Catalan numbers tell you how many different BST shapes are possible for a given number of values

Classic Patterns

• Preorder + Inorder or Postorder + Inorder - always rebuilds a unique tree
• Preorder + Postorder alone - ambiguous, unless the tree is full
• BST insert and search - compare and go left or right, just like binary search
• BST delete with two children - replace with the inorder successor, then delete the successor
• Catalan recurrence - pick a root, multiply left and right subtree counts, sum over every possible root

Interview Tips

• Know that inorder traversal on a BST always returns sorted values
• Be ready to explain why preorder + postorder alone cannot rebuild a unique tree
• Mention the hashmap trick to speed up tree construction from O(n squared) to O(n)
• Always handle all three BST delete cases, especially the two-children case
• Remember the Catalan formula: C(n) = sum of C(i-1) * C(n-i), with C(0) = 1
• A BST built from already-sorted data becomes skewed and slow, so mention this worst case