1 What is a Tree

Concept

• In data structures, a "Tree" is a crucial non-linear data structure that models data collections with tree-like characteristics. In tree structures, each element is called a node, and nodes are connected through specific relationships, typically described as "parent-child" relationships.
• A tree is a hierarchical collection of n (n≥0) finite nodes. It has a special node called the root node, while the remaining nodes are divided into m (m≥0) disjoint finite sets T1, T2, …, Tm, where each subset Ti (1≤i≤m) is itself a tree according to this definition, known as a subtree of the root.

Characteristics

1. Hierarchy: Nodes in a tree are organized hierarchically, with the root node at the top level and leaf nodes at the bottom level.
2. Acyclicity: In a tree, except for the root node, each node has exactly one parent node; no node is its own ancestor or descendant.
3. Disjoint Subtrees: Nodes between any two subtrees do not intersect.

2 Important Terminology

1. Node

   • Each element in a tree is a node.
   • A node may contain a value or a set of values, along with links to its child nodes.

2. Root Node

   • The only node in the tree without a parent node.
   • It typically serves as the entry point to the tree.

3. Child Node

   • A node can have zero or more child nodes.
   • Child nodes are connected to their parent node via edges.

4. Parent Node

   • The node immediately above a child node.
   • Every node except the root has one parent node.

5. Sibling Nodes

   • Nodes that share the same parent node.

6. Leaf Node

   • A node with no child nodes.
   • They are located at the lowest level of the tree.

7. Degree

   • The number of child nodes of a node.
   • Leaf nodes have a degree of 0.
   • Example: In a binary tree, each node has at most two child nodes (a left child and a right child), so the maximum degree of a node in a binary tree is 2. However, in a general tree (also known as an N-ary tree), a node's degreee can be greater than 2, depending on the tree's definition and context.

8. Degree of a Tree

   • The maximum degree among all nodes in the tree.

9. Level

   • Starting from the root node, the root is at level 1, its children are at level 2, and so on.

10. Depth or Height

    • The maximum level number among all nodes in the tree.
    • The depth of the root node is 0, the depth of its direct children is 1, and so on.

11. Path

    • A sequence of nodes from one node to another.
    • The path length is the number of nodes in the path minus one.

12. Forest

    • A collection of one or more disjoint trees.

13. Node Height: The longest path from the node to a leaf node.

14. Node Depth: The number of edges from the root node to that node.

15. Node Level: The node's depth plus 1.

16. Tree Height: The height of the root node.

3 Different Types of Trees

1. Binary Tree: A tree where each node has at most two child nodes.

   • Each node has at most two child nodes, typically called the left child and right child.
   • Subtrees cannot intersect.
   • Except for the root node, each node has exactly one parent node.
   • A tree with N nodes has N-1 edges.
   • The number of subtrees of a node is called the node's degree; in a binary tree, the maximum degree of a node is 2.

2. Binary Search Tree (BST): A special form of binary tree where, for each node in the tree, all values in its left subtree are less than its value, and all values in its right subtree are greater than its value.

3. Balanced Binary Tree: A special type of binary search tree where the height difference between the two subtrees of any node is at most 1. Common balanced binary trees include AVL trees and Red-Black trees.

4. Complete Binary Tree: A binary tree where all levels except possibly the last are fully filled, and all nodes in the last level are as far left as possible.

   • Numbering Property: For a complete binary tree of depth h, nodes are numbered from 1 to 2^h-1. For any node i with number i, its left child is numbered 2i, and its right child is numbered 2i+1.
   • Parent-Child Relationship: For any node i with number i, its parent node is numbered i/2 (rounded down).
   • Height: The height of a complete binary tree is log(n+1) (base 2), where n is the number of nodes.
   • Storage Method: Complete binary trees can be stored using arrays, enabling fast access and modification.

5. Full Binary Tree: A binary tree where every node other than the leaves has two children.

   • The number of nodes at each level reaches its maximum.
   • Nodes are either leaf nodes (no children) or nodes with degree 2 (two children).

6. N-ary Tree: A tree where each node can have N child nodes, with N being an integer greater than 1.

7. B-Tree and B+ Tree: Balanced multiway search trees used in databases and file systems. They allow each node to have multiple child nodes and keys, enabling efficient insertion, deletion, and search operations.

8. Heap: A special tree-based data structure typically used to implement priority queues. A heap is a complete binary tree that satisfies the heap property: the value of a parent node is always greater than or equal to (max-heap) or less than or equal to (min-heap) the values of its child nodes.

4 Binary Tree Traversal

4.1 Preorder Traversal

Preorder traversal order: Root node, Left node, Right node

/**
 * Preorder traversal
 * @param node
 */
public void preorderTraversal(TreeNode<T> node) {
    printNode(node);
    if (node.left != null) {
        preorderTraversal(node.left);
    }
    if (node.right != null) {
        preorderTraversal(node.right);
    }
}

4.2 Inorder Traversal

Inorder traversal order: Left node, Root node, Right node

/**
 * Inorder traversal
 */
public void inorderTraversal(TreeNode<T> node) {
    if (node == null) {
        return;
    }
    if (node.left != null) {
        inorderTraversal(node.left);
    }
    printNode(node);
    if (node.right != null) {
        inorderTraversal(node.right);
    }
}

4.3 Postorder Traversal

Postorder traversal order: Left node, Right node, Root node

/**
 * Postorder traversal
 */
public void postorderTraversal(TreeNode<T> node) {
    if (node == null) {
        return;
    }
    if (node.left != null) {
        postorderTraversal(node.left);
    }
    if (node.right != null) {
        postorderTraversal(node.right);
    }
    printNode(node);
}

4.4 Level Order Traversal

Level order traversal: Also known as breadth-first traversal

/**
 * Level order traversal
 */
public void levelOrderTraversal(TreeNode<T> node) {
    if (node == null) {
        return;
    }
    printNode(node);
    Queue<TreeNode<T>> nodeQueue = new LinkedList<>();
    nodeQueue.add(node);
    while (!nodeQueue.isEmpty()) {
        TreeNode<T> current = nodeQueue.poll();
        if (current.left != null) {
            printNode(current.left);
            nodeQueue.add(current.left);
        }
        if (current.right != null) {
            printNode(current.right);
            nodeQueue.add(current.right);
        }
    }
}

4.5 Complete Code Example

package data.structures.tree;

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

/**
 * Binary Tree Example
 *              A
 *            /   \
 *           B     E
 *            \     \
 *            C      F
 *           /      /
 *          D      G
 *               /  \
 *              H    K
 * Preorder traversal:
 * A B C D E F G H K
 * Inorder traversal:
 * B D C A E H G K F
 * Postorder traversal:
 * D C B H K G F E A
 * Level order traversal:
 * A B E C F D G H K
 */
public class BinaryTreeDemo<T> {

    /**
     * Preorder traversal
     * @param node
     */
    public void preorderTraversal(TreeNode<T> node) {
        printNode(node);
        if (node.left != null) {
            preorderTraversal(node.left);
        }
        if (node.right != null) {
            preorderTraversal(node.right);
        }
    }

    /**
     * Inorder traversal
     */
    public void inorderTraversal(TreeNode<T> node) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            inorderTraversal(node.left);
        }
        printNode(node);
        if (node.right != null) {
            inorderTraversal(node.right);
        }
    }

    /**
     * Postorder traversal
     */
    public void postorderTraversal(TreeNode<T> node) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            postorderTraversal(node.left);
        }
        if (node.right != null) {
            postorderTraversal(node.right);
        }
        printNode(node);
    }

    /**
     * Level order traversal
     */
    public void levelOrderTraversal(TreeNode<T> node) {
        if (node == null) {
            return;
        }
        printNode(node);
        Queue<TreeNode<T>> nodeQueue = new LinkedList<>();
        nodeQueue.add(node);
        while (!nodeQueue.isEmpty()) {
            TreeNode<T> current = nodeQueue.poll();
            if (current.left != null) {
                printNode(current.left);
                nodeQueue.add(current.left);
            }
            if (current.right != null) {
                printNode(current.right);
                nodeQueue.add(current.right);
            }
        }
    }

    /**
     * Print node data
     * @param node
     */
    public void printNode(TreeNode<T> node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
    }

    public static void main(String[] args) {
        TreeNode<String> D = new TreeNode<>("D", null, null);
        TreeNode<String> H = new TreeNode<>("H", null, null);
        TreeNode<String> K = new TreeNode<>("K", null, null);
        TreeNode<String> C = new TreeNode<>("C", D, null);
        TreeNode<String> G = new TreeNode<>("G", H, K);
        TreeNode<String> B = new TreeNode<>("B", null, C);
        TreeNode<String> F = new TreeNode<>("F", G, null);
        TreeNode<String> E = new TreeNode<>("E", null, F);
        TreeNode<String> A = new TreeNode<>("A", B, E);
        
        BinaryTreeDemo<String> treeDemo = new BinaryTreeDemo<>();
        
        System.out.println("Preorder traversal:");
        treeDemo.preorderTraversal(A); // A B C D E F G H K
        System.out.println();
        
        System.out.println("Inorder traversal:");
        treeDemo.inorderTraversal(A); // B D C A E H G K F
        System.out.println();
        
        System.out.println("Postorder traversal:");
        treeDemo.postorderTraversal(A); // D C B H K G F E A
        System.out.println();
        
        System.out.println("Level order traversal:");
        treeDemo.levelOrderTraversal(A); // A B E C F D G H K
        System.out.println();
    }
}

class TreeNode<T> {
    T data;
    TreeNode<T> left;
    TreeNode<T> right;
    
    public TreeNode(T data) {
        this.data = data;
    }
    
    public TreeNode(T data, TreeNode<T> left, TreeNode<T> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public TreeNode<T> getLeft() {
        return left;
    }

    public void setLeft(TreeNode<T> left) {
        this.left = left;
    }

    public TreeNode<T> getRight() {
        return right;
    }

    public void setRight(TreeNode<T> right) {
        this.right = right;
    }
}