DSA Trees and Binary Search Trees

A tree stores data in a hierarchy, with one item at the top and branches below it.

What is a Tree?

Think of a family tree, or the folders on your computer: one main folder holds other folders, which hold more folders and files.

Example

text

            CEO
          /     \
      Manager   Manager
      /    \        \
   Staff  Staff    Staff

Tree Words

Word	Meaning
Node	One item in the tree
Root	The top node, with no parent
Parent / child	A node directly above / below another
Leaf	A node with no children
Edge	The link between a parent and a child
Height	The number of edges on the longest path from the root to a leaf
Subtree	A node together with everything below it

Binary Trees

In a binary tree, each node has at most two children, called the left and right child.

Example

python

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

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)

print(root.value, root.left.value, root.right.value, root.left.left.value)

Output

1 2 3 4

Binary Search Trees (BST)

A binary search tree follows one rule at every node:

All values in the left subtree are smaller
All values in the right subtree are bigger

This rule lets you search like binary search: at each node, go left or right and ignore the other side.

Example

python

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

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

def search(node, value):
    if node is None:
        return False
    if value == node.value:
        return True
    if value < node.value:
        return search(node.left, value)
    return search(node.right, value)

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)

print(search(root, 60))
print(search(root, 65))

Output

True
False

The tree built above looks like this:

Example

text

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

Tree Traversals

Traversal means visiting every node. The three depth-first orders differ in when you visit the node itself:

Order	Steps	Result for the tree above
In-order	left, node, right	20 30 40 50 60 70 80
Pre-order	node, left, right	50 30 20 40 70 60 80
Post-order	left, right, node	20 40 30 60 80 70 50

Example

python

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

def in_order(node, out):
    if node:
        in_order(node.left, out)
        out.append(node.value)
        in_order(node.right, out)
    return out

def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

root = Node(50,
            Node(30, Node(20), Node(40)),
            Node(70, Node(60), Node(80)))
print(in_order(root, []))
print("Height:", height(root))

Output

[20, 30, 40, 50, 60, 70, 80]
Height: 2

In-order traversal of a BST always gives the values in sorted order. This is a very useful fact in interviews.

Costs

Operation	Balanced BST	Unbalanced BST (like a chain)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

If you insert already sorted values (10, 20, 30, 40...), each new node goes to the right and the tree becomes a long chain. Self-balancing trees, such as AVL and red-black trees, fix this automatically.

Exercise

In a binary search tree, where are values smaller than a node stored?

In its left subtreeIn its right subtreeIn the root onlyAnywhere in the tree