Binary Trees

Some of the data structures which are popular in interviews are trees. Trees are, in essence graphs which don't have cycles in them. They contain nodes with edges and normally if a tree has n nodes then it will have n - 1 edges.

Trees in computer science have varied applications some of which include representing file directories or web pages. There are also different kind of trees ranging from Binary Search Trees, AVL Trees, Red Black Trees, Rooted Trees (directing to or from the root node) etc.

In this article, we will talk about binary trees. Before we proceed with binary trees we will briefly talk about how trees in general can be stored.

1. Edge List

For the tree shown, this would be

[
  (A, B),
  (B, C),
  (C, D),
]

where each node is shown with its neighbour. This technique enables quick traversal over the tree and it is cheap to store. However, it lacks the ability to query all neighbours of a given node. This leads us to the second storage technique which addresses this issue.

1. Adjacency List This technique allows for storing of nodes by mapping a node to its neighbours. For the tree shown below,

the node A will have 3 mappings to its neighbours/children.

A -> [B, C, D]

1. Adjacency Matrix Another way of representing trees is via Adjacency Matrix which is essentially representing nodes using a list.

And now on to binary trees, they are a type of rooted trees and are easy to implement using a recursive strategy. In a binary tree, every node has at most 2 nodes. They offer excellent insertion, removal and access time complexities.

Another variation includes a binary search (offers quick traversal) tree which follows the BST invariant i.e.

let n be a node in a binary search tree
n.left.val <= n.val <= n.right.val
For uniqueness in the tree structure, this can be modified to
n.left.val < n.val < n.right.val

Binary trees can be represented using a pointer reference. A pointer is attached to the root node which points to the left and right child nodes, with each node containing the data assigned to it.
The following code snippet shows a binary tree class with methods for insertion and deletion. Tree traversal is achieved by either breadth first or depth first search.

import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree {
    Node root;

    BinaryTree() {
        this.root = null;
    }

    BinaryTree(int val) {
        this.root = new Node(val);
    }

    public void insert(int val) {
        if (this.root == null) {
            this.root = new Node(val);
        }

        Queue<Node> q = new LinkedList<>();
        Node temp = this.root;
        q.add(temp);

        while (!q.isEmpty()) {
            temp = q.peek();
            q.remove();

            if (temp.left == null) {
                temp.left = new Node(val);
                break;
            } else {
                q.add(temp.left);
            }

            if (temp.right == null) {
                temp.right = new Node(val);
                break;
            } else {
                q.add(temp.right);
            }
        }
    }

    public void delete(int val) {
        if (this.root == null) {
            return;
        }

        if (this.root.left == null && this.root.right == null) {
            if (this.root.val == val) {
                this.root = null;
                return;
            } else {
                return;
            }
        }

        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        Node temp = null, keyNode = null;

        while (!q.isEmpty()) {
            temp = q.peek();
            q.remove();

            if (temp.val == val) {
                keyNode = temp;
            }

            if (temp.left != null) {
                q.add(temp.left);
            }

            if (temp.right != null) {
                q.add(temp.right);
            }
        }

        if (keyNode != null) {
            int x = temp.val;
            deleteDeepest(root, temp);
            keyNode.val = x;
        }
    }
    static void deleteDeepest(Node root, Node delNode) {
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);

        Node temp = null;

        while (!q.isEmpty()) {
            temp = q.peek();
            q.remove();

            if (temp == delNode) {
                temp = null;
                return;
            }
            if (temp.right!=null) {
                if (temp.right == delNode) {
                    temp.right = null;
                    return;
                }
                else {
                    q.add(temp.right);
                }
            }
            if (temp.left != null) {
                if (temp.left == delNode) {
                    temp.left = null;
                    return;
                }
                else {
                    q.add(temp.left);
                }
            }
        }
    }
}
// Time complexity for insertion: O(h)
// Time complexity for deletion: O(n)
// where h = height of the tree and n = number of nodes

Note: This is part of my notes on data structures and algorithms. This may be modified as I learn more.