Tree

Last Updated: 2024-01-15

The most basic trees: Binary Tree and Binary Search Tree. For more advanced trees, like B-Tree, Merkel Tree, check Advanced Data Structures

Tree Definition

Java

class BinaryTree {

    private Node root;

    public BinaryTree() {
        root = null;
    }

    private static class Node {
        Node left;
        Node right;
        int data;

        Node(int newdata) {
            left = null;
            right = null;
            data = newdata;
        }
    }
}

Go

type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}

Python

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None

Insert Into Binary Search Tree

public Node insert(Node node, int data) {
    if (node == null) {
        node = new Node(data);
    } else {
        if (data <= node.data) {
            node.left = insert(node.left, data);
        } else {
            node.right = insert(node.right, data);
        }
    }
    return node;
}

Traversal

In-order

public void inorder(Node node) {
    if (node == null)
        return;
    inorder(node.left);
    System.out.println(node.data);
    inorder(node.right);
    return;
}

Pre-order

public void preorder(Node node){
    if (node == null)
        return;
    System.out.println(node.data);
    preorder(node.left);
    preorder(node.right);
    return;
}

Post-order

public void postorder(Node node){
    if (node == null)
        return;
    postorder(node.left);
    postorder(node.right);
    System.out.println(node.data);
    return;
}

Min/Max Depth

public int maxDepth() {
    return maxDepth(root);
}

public int maxDepth(Node node){
    if (node == null)
        return 0;
    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}


public int minDepth() {
    return minDepth(root);
}

public int minDepth(Node node){
    if (node == null)
        return 0;
    return 1 + Math.min(minDepth(node.left), minDepth(node.right));
}

Check Balance

public boolean isBalanced() {
    return (maxDepth(root) - minDepth(root) <= 1);
}

or

public boolean isBalanced(TreeNode root) {
    return balanced(root) != -1;
}

private int balanced(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = balanced(root.left);
    int right = balanced(root.right);

    if (left == -1 || right == -1) {
        return -1;
    }

    if (Math.abs(left - right) <= 1) {
        return Math.max(left, right) + 1;
    } else {
        return -1;
    }
}

Has Path Sum

Given a tree and a sum, returns true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum.

public boolean hasPathSum(int sum) {
    return hasPathSum(root, sum);
}

public boolean hasPathSum(Node node, int sum) {
    if (node == null) return (sum == 0);
    return hasPathSum(node.left, sum - node.data) || hasPathSum(node.right, sum - node.data);
}

Size

public int size(Node node){
    if (node == null)
        return 0;
    return 1 + size(node.left) + size(node.right);
}

Print Path

public void printPaths() {
    int[] path = new int[size()];
    printPaths(root, path, 0);
}

public void printPaths(Node node, int[] path, int len) {
    if (node == null)
        return;

    path[len++] = node.data;
    if (node.left == null && node.right == null) {
        for (int i = 0; i < len; i++){
            System.out.print(path[i] + " ");
        }
        System.out.println();
        return;
    } else {
        printPaths(node.left, path, len);
        printPaths(node.right, path, len);
    }
}

Check Same

public boolean sameTree(Node a, Node b) {
    if (a == null && b == null)
        return true;
    else if (a != null && b != null) {
        return (a.data == b.data &&
                sameTree(a.left, b.left) &&
                sameTree(a.right, b.right));
    } else {
        return false;
    }
}

Count Trees

For the key values 1...numKeys, how many structurally unique binary search trees are possible that store those keys?

Strategy: consider that each value could be the root. Recursively find the size of the left and right subtrees.

public static int countTrees(int n) {
    if (n <= 1)
        return 1;
    int sum = 0;
    for (int i = 1; i <= n; i++){
        int left = countTrees(i-1);
        int right = countTrees(n-i);
        sum += left * right;
    }
    return sum;
}

IsComplete

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class IsComplete {

    class Node {
        Node left, right;

        public Node(Node left, Node right) {
            this.left = left;
            this.right = right;
        }
    }

    public static boolean isComplete(Node root) {
        Queue<Node> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            Node head = queue.poll();

            // Stop as soon as we see first null
            if (head == null) {
                break;
            }

            queue.offer(head.left);
            queue.offer(head.right);
        }

        // the remaining elements in the queue should all be null
        while (!queue.isEmpty()) {
            Node head = queue.poll();

            if (head != null) {
                return false;
            }
        }
        return true;
    }

}