Trees

A non-linear data structure in which each node points to multiple nodes.

Terminology

Root: The top node of the tree, with no parents.
Edge: refers to a connection between two nodes.
Leaf node: A node with no children.
Siblings: children of the same parent.
Ancestor: A node p is an ancestor of node q if p is on the path from the root to q. The node q is a descendant of p.
Depth: length of the path from the root to a node.
Size of a node: number of descendants of a node.
Skew Trees: A tree where all nodes have only one child.

Binary Trees

A tree is called a binary tree if each node has at most two children. The children are referred to as the left child and the right child.

graph TD;
    A --> B;
    A --> C;
    B --> D;
    B --> E;
    C --> F;

Types

Strict BT: Each node has either 0 or 2 children.
Full BT: Each node has 2 children, and all leaf nodes are at the same level.

Properties

• The maximum number of nodes at level l is 2^l.
• The maximum number of nodes in a binary tree of height h is \(2^{h+1} - 1\). This will happen when the tree is a full binary tree.
• Number of leaf nodes in a full BT is \(2^h\)

Structure

class Node {
    int data;
    Node left;
    Node right;
}

Traversals

Pre-order Traversal

DLR traversal. Each node is processed before its children.

// Iterative version
void preOrder(Node root) {
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        System.out.print(node.data + " ");
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

In-order Traversal

LDR traversal. The node is processed between its children.

// Iterative version
void inOrder(Node root) {
    Stack<Node> stack = new Stack<>();
    Node current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        System.out.print(current.data + " ");
        current = current.right;
    }
}

Post-order Traversal

LRD traversal. The node is processed after its children. In preorder and inorder, after popping the node we don't need to visit it again. But in postorder, we need to visit the node after visiting its children.

// Iterative version
void postOrder(Node root) {
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    Stack<Integer> output = new Stack<>();
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        output.push(node.data);
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }
    while (!output.isEmpty()) {
        System.out.print(output.pop() + " ");
    }
}

Level-order Traversal

Use Queue to traverse the tree level by level.

void levelOrder(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.print(node.data + " ");
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

Binary Search Trees (BST)

BST is a BT in which all elements in left subtree are less than root and all elements in right subtree are more than the root. This property should be satisfied by every node in BT for it to be a BST.

Searching for an element in BST takes O(log n) where as in BT it is O(n).

Predecessor — max in left subtree or first left ancestor

AVL (Adelson-Velskii and Landis) Trees

Height balanced trees are represented with HB(k), where k is the difference between left subtree and right subtree height. k is called balance factor.

If k=1, such binary search trees are called AVL trees.

Properties

A BT is said to be AVL tree if:

• It is a BST
• For any node X, the height of the left subtree of X and the height of the right subtree of X differ by at most 1.

Min & Max nodes

Let h be height of an AVL tree. N(h) = number of nodes.

To get minimum number of nodes we fill left subtree with height h-1 and right with height h-2.
N(h) = N(h-1) + N(h-2) + 1
N(h) = O(\(1.1618^h\))
=> h = O(log n)

To get maximum number of nodes we fill both left and right subtree with height h-1.
N(h) = 2*N(h-1) + 1
N(h) = O(\(2^h\))
=> h = O(log n)

When we insert/delete a node we need to rebalance the tree. Rotations is the technique used to restore the AVL tree property. To restore, we start at the insertion point and keep going to the root. If we fix the first node that violates the AVL property then all nodes on the path automatically get fixed.

Rotations

Single Rotations: Left Left Rotation, Right Right Rotation

fun singleRotateLeft(x: AVLNode): AVLNode {
    val w = x.left
    x.left = w.right
    w.right = x
    return w
}

fun singleRotateRight(x: AVLNode): AVLNode {
    val w = x.right
    x.right = w.left
    w.left = x
    return w
}

Double Rotations: Left Right Rotation, Right Left Rotation

fun doubleRotateWithLeft(z: AVLNode): AVLNode {
    z.left = singleRotateRight(z.left)
    return singleRotateLeft(z)
}

fun doubleRotateWithRight(z: AVLNode): AVLNode {
    z.right = singleRotateLeft(z.right)
    return singleRotateLeft(z)
}

Generic Trees (N-ary Trees)

Each node can any number of children.

Structure

Since we don't know how many children each node has, creating a pointer array or set of pointers in the node is a memory wastage. Even the number of child pointers to be created is unknown at the time of class declaration.

So instead for each node we create a first child and next sibling pointers.

class TreeNode {
    int data;
    TreeNode firstChild;
    TreeNode nextSibling;
}

This structure is similar to a binary tree. So any m-ary tree can be represented as a binary tree.

Expression Trees

A tree representing an expression. Leaf nodes are operands and internal nodes are operators.