All about Tree Data Structures

What is a Tree data structure?

A tree is a non-linear data structure that consists of nodes connected by edges, where each node can have zero or more children nodes. The topmost node of a tree is called the root node, and nodes with no children are called leaf nodes.

There are several types of trees:

Binary Tree: A binary tree is a tree in which each node has at most two children.

Binary Search Tree (BST): A binary search tree is a binary tree in which the left subtree of a node contains only nodes with keys less than the node's key, and the right subtree contains only nodes with keys greater than the node's key.

AVL Tree: An AVL tree is a self-balancing binary search tree in which the heights of the left and right subtrees of any node differ by at most one.

B-Tree: A B-tree is a self-balancing tree in which each node can have more than two children.

Trie: A trie is a tree-like data structure used to store a set of strings, where each node represents a single character and the root node represents the empty string.

Some common operations on a tree include:

Traversing: This involves visiting every node in a tree in a particular order. There are three common types of tree traversal: preorder, inorder, and postorder.

Searching: This involves finding a specific node in a tree. In a binary search tree, searching can be done in O(log n) time.

Inserting: This involves adding a new node to a tree in the appropriate location based on the value of its key.

Deleting: This involves removing a node from a tree. Depending on the type of tree, deleting a node may require rebalancing the tree to maintain certain properties.

Finding minimum/maximum: This involves finding the node with the minimum or maximum key value in a tree.

Height calculation: This involves finding the height of a tree, which is the length of the longest path from the root node to a leaf node.

There are three common types of tree traversal:

Preorder traversal: In a preorder traversal, we visit the root node first, then recursively traverse the left subtree, followed by the right subtree.

The pseudocode for a recursive preorder traversal is:

preorder(node):
    if node is not null:
        visit(node)
        preorder(node.left)
        preorder(node.right)

Inorder traversal: In an inorder traversal, we recursively traverse the left subtree, then visit the root node, and finally recursively traverse the right subtree. The pseudocode for a recursive inorder traversal is:

inorder(node):
    if node is not null:
        inorder(node.left)
        visit(node)
        inorder(node.right)

Postorder traversal: In a postorder traversal, we recursively traverse the left and right subtrees first, and then visit the root node. The pseudocode for a recursive postorder traversal is:

postorder(node):
    if node is not null:
        postorder(node.left)
        postorder(node.right)
        visit(node)

Code representation of a Tree:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Example code of Tree data structure with Search, Delete and Insert operation in a Binary Search Tree (BST).

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class BST {
    private TreeNode root;
    
    public BST() {
        root = null;
    }
    
    public void Insert(int val) {
        if (root == null) {
            root = new TreeNode(val);
        }
        else {
            InsertHelper(root, val);
        }
    }
    
    private void InsertHelper(TreeNode node, int val) {
        if (val < node.val) {
            if (node.left == null) {
                node.left = new TreeNode(val);
            }
            else {
                InsertHelper(node.left, val);
            }
        }
        else {
            if (node.right == null) {
                node.right = new TreeNode(val);
            }
            else {
                InsertHelper(node.right, val);
            }
        }
    }
    
    public TreeNode Search(int val) {
        return SearchHelper(root, val);
    }
    
    private TreeNode SearchHelper(TreeNode node, int val) {
        if (node == null || node.val == val) {
            return node;
        }
        else if (val < node.val) {
            return SearchHelper(node.left, val);
        }
        else {
            return SearchHelper(node.right, val);
        }
    }
    
    public void Delete(int val) {
        root = DeleteHelper(root, val);
    }
    
    private TreeNode DeleteHelper(TreeNode node, int val) {
        if (node == null) {
            return null;
        }
        if (val < node.val) {
            node.left = DeleteHelper(node.left, val);
        }
        else if (val > node.val) {
            node.right = DeleteHelper(node.right, val);
        }
        else {
            if (node.left == null) {
                return node.right;
            }
            else if (node.right == null) {
                return node.left;
            }
            else {
                TreeNode minNode = node.right;
                while (minNode.left != null) {
                    minNode = minNode.left;
                }
                node.val = minNode.val;
                node.right = DeleteHelper(node.right, minNode.val);
            }
        }
        return node;
    }
}

Other Data Structures

Array

Azam's Blog on System Design & Architecture

Search This Blog