Binary Trees

Binary Search Trees

Binary search trees (BSTs) are a special type of binary tree that satisfies an additional constraint: the nodes in the left subtree must have key values less than the key value of the parent, and the nodes in the right subtree must have key values greater than the key value of the parent.

In other words, in a BST, the left child of any node has a smaller value, and the right child has a larger value. This property of BSTs enables efficient searching, insertion, and deletion operations.

BSTs are commonly used in various applications, such as implementing symbol tables, dictionaries, and binary search algorithms.

Here's an example of a binary search tree:

     50
   /     \
  30     70
 / \    / \
20  40  60  80

To implement a BST, we need to define a class that represents a node in the tree and another class that represents the binary search tree itself.

Let's create a BST class with the following functionalities:

• void insert(int data): Inserts a new node with the given data into the BST
• void print(): Prints the contents of the BST in sorted order

Here's an implementation of the BST class in Java:

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

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

class BST {
    Node root;

    BST() {
        this.root = null;
    }

    void insert(int data) {
        this.root = insertRec(this.root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }

        if (data < root.data) {
            root.left = insertRec(root.left, data);
        } else if (data > root.data) {
            root.right = insertRec(root.right, data);
        }

        return root;
    }

    void print() {
        printRec(this.root);
    }

    void printRec(Node root) {
        if (root != null) {
            printRec(root.left);
            System.out.print(root.data + " ");
            printRec(root.right);
        }
    }
}

```java
class Main {
    public static void main(String[] args) {
        // Binary Search Tree
        BST bst = new BST();
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);

        // Print the tree
        bst.print();
    }

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

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

    static class BST {
        Node root;

        BST() {
            this.root = null;
        }

        void insert(int data) {
            this.root = insertRec(this.root, data);
        }

        Node insertRec(Node root, int data) {
            if (root == null) {
                root = new Node(data);
                return root;
            }

            if (data < root.data) {
                root.left = insertRec(root.left, data);
            } else if (data > root.data) {
                root.right = insertRec(root.right, data);
            }

            return root;
        }

        void print() {
            printRec(this.root);
        }

        void printRec(Node root) {
            if (root != null) {
                printRec(root.left);
                System.out.print(root.data + " ");
                printRec(root.right);
            }
        }
    }
}
```

In a binary search tree (BST), for any node, the values of its left sub-tree are ___________ than the value of the node, and the values of its right sub-tree are ___________ than the value of the node.

Solution: smaller, larger

Explanation: In a binary search tree (BST), the values of the nodes in the left sub-tree are smaller than the value of the node, and the values of the nodes in the right sub-tree are larger than the value of the node. This property of BSTs enables efficient searching, insertion, and deletion operations.

AVL Trees

AVL trees are a type of self-balancing binary search tree. They were the first self-balancing trees to be invented, with the initials AVL standing for the creators, Adelson-Velsky and Landis.

Self-Balancing

The key feature of AVL trees is that they always maintain balance. A balanced tree is a tree where the heights of the left and right subtrees of any node differ by at most 1.

Maintaining balance is important because it ensures that the time complexity of basic operations remains efficient. In an unbalanced binary search tree, operations like search, insert, and delete can take longer to perform, reducing the efficiency of the tree.

Height-Balanced

AVL trees are height-balanced, meaning that the heights of the left and right subtrees of any node differ by at most 1. This balance is achieved through a process called rotation.

When a new node is inserted, the AVL tree checks for any imbalances and performs rotations to restore balance. There are four possible rotations: left rotation, right rotation, left-right rotation, and right-left rotation.

Advantages of AVL Trees

AVL trees offer several advantages:

• Efficient searching, insertion, and deletion operations with a guaranteed time complexity of O(log n)
• Automatic balancing ensures optimal performance
• Well-suited for scenarios where the tree is frequently modified

Example

Let's take a look at an example of an AVL tree:

      30
     /  \
    20   40
   / \     \
  10  25    50

In this example, the AVL tree has a height of 2, and the left and right subtrees of the root node have a height difference of 1. This is an example of a balanced AVL tree.

AVL trees are commonly used in various applications, such as in database systems, as indexes in search algorithms, and in in-memory data structures.

To implement an AVL tree, we need to define a class that represents a node in the tree and another class that represents the AVL tree itself. Here's an implementation of the Node and AVLTree classes in Java:

// Node class
class Node {
    int data;
    int height;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
        this.height = 1;
        this.left = null;
        this.right = null;
    }
}

// AVL Tree class
class AVLTree {
    Node root;

    // Insert method, rotation methods, and other functionality
}

In the implementation above, the Node class represents a node in the AVL tree, while the AVLTree class represents the tree itself. The Node class stores the data, height, and references to the left and right child nodes.

To maintain balance, the AVLTree class performs rotations when necessary during the insertion of new nodes. These rotations ensure that the AVL tree remains height-balanced and efficient for searching, insertion, and deletion operations.

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

// Node class
class Node {
    int data;
    int height;
    Node left;
    Node right;

    // Constructor
class Node {
    int data;
    int height;
    Node left;
    Node right;

    // Constructor
class Node {
    int data;
    int height;
    Node left;
    Node right;

    // Constructor
class Node {
    int data;
    int height;
    Node left;
    Node right;

    // Constructor
class Node {
    int data;
    int height;
    Node left;
    Node right;

    // Constructor
    public Node(int data) {
        this.data = data;
        this.height = 1;
        this.left = null;
        this.right = null;
    }
}


// AVL Tree class
class AVLTree {
    Node root;

    // Get height of the tree
    int height(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    // Get the balance factor of a node
    int getBalance(Node node) {
        if (node == null) {
            return 0;
        }
        return height(node.left) - height(node.right);
    }

    // Update the height of a node
    void updateHeight(Node node) {
        if (node != null) {
            node.height = Math.max(height(node.left), height(node.right)) + 1;
        }
    }

    // Right rotate a subtree rooted with y
    Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // Perform rotation
        x.right = y;
        y.left = T2;

        // Update heights
        updateHeight(y);
        updateHeight(x);

        // Return new root
        return x;
    }

    // Left rotate a subtree rooted with x
    Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // Perform rotation
        y.left = x;
        x.right = T2;

        // Update heights
        updateHeight(x);
        updateHeight(y);

        // Return new root
        return y;
    }

    // Insert a node
    Node insert(Node node, int key) {
        // Perform the normal BST insertion
        if (node == null) {
            return new Node(key);
        }

        if (key < node.data) {
            node.left = insert(node.left, key);
        } else if (key > node.data) {
            node.right = insert(node.right, key);
        } else {
            // Duplicate keys are not allowed in AVL Tree
            return node;
        }

        // Update height
        updateHeight(node);

        // Balance the tree if needed
        int balance = getBalance(node);

        // Left Left Case
        if (balance > 1 && key < node.left.data) {
            return rightRotate(node);
        }

        // Right Right Case
        if (balance < -1 && key > node.right.data) {
            return leftRotate(node);
        }

        // Left Right Case
        if (balance > 1 && key > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // Right Left Case
        if (balance < -1 && key < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    // Print the tree
    void printLevelOrder() {
        if (root == null) {
            System.out.println("Tree is empty");
            return;
        }

        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);
            }
        }
    }

    // Driver code
class Main {
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 50);
        tree.root = tree.insert(tree.root, 25);

        System.out.println("Level order traversal of the constructed AVL tree:");
        tree.printLevelOrder();
    }
}
```

The self-balancing feature of AVL trees helps maintain the time complexity of basic operations.

Red-Black Trees

Red-Black trees are balanced binary search trees that guarantee logarithmic time complexity for basic operations like search, insert, and delete. They are self-balancing trees that maintain balance through a set of rules and operations.

Characteristics of Red-Black Trees

Red-Black trees have the following characteristics:

1. Node Colors: Each node in the tree is either red or black
2. Root Color: The root node is always black
3. Leaf Nodes: The leaf nodes (null nodes) are considered black
4. Red Node Constraints: No two adjacent nodes can be red. In other words, a red node cannot have a red parent or red children
5. Black Node Constraints: For any given node, all paths from that node to its descendant leaf nodes must contain the same number of black nodes

Balancing Operations

Red-Black trees use a set of balancing operations to maintain their properties. These operations include:

• Rotations: Left rotations and right rotations are performed to maintain balance when necessary
• Recoloring: Changing the colors of nodes within the tree to restore balance

Red-Black trees are commonly used in various applications, such as in database indexing, where the tree needs to be efficiently balanced and allow quick access to data.

Let's take a look at an example of a Red-Black tree:

          20
        /    \
       10      40
      /  \     /  \
     5   15   30   50

In this example, the Red-Black tree is balanced, and all the red-black tree properties are satisfied.

To implement a Red-Black tree, we can define a class that represents a node in the tree and another class that represents the Red-Black tree itself. Here's an example implementation in Java:

class Node<E> {
    E data;
    Node<E> left;
    Node<E> right;
    Node<E> parent;
    int color;

    public Node(E data) {
        this.data = data;
        left = right = parent = null;
        color = 1;
    }
}

class RedBlackTree<E extends Comparable<E>> {
    Node<E> root;

    // Red-Black Tree methods and functionality
}

In the implementation above, the Node class represents a node in the Red-Black tree, and the RedBlackTree class represents the tree itself. The Node class stores the data, references to the left and right child nodes, the parent node, and the color of the node.

To maintain balance, the RedBlackTree class performs rotations and recoloring operations when necessary during node insertion and deletion. These operations ensure that the Red-Black tree remains balanced and efficient for searching, insertion, and deletion operations.

Now you have a basic understanding of Red-Black trees and their characteristics!

```java
public class Main {
    public static void main(String[] args) {
        // Replace with your Java logic here
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(40);
        tree.insert(50);
        tree.insert(60);
        tree.insert(70);

        System.out.println("Red-Black Tree:");
        tree.printTree();
    }
}

class RedBlackTree<E extends Comparable<E>> {
    // Red-Black Tree implementation
    // Replace with the Red-Black Tree implementation relevant to the content
}
```

The root node of a Red-Black tree must always be red.

Insertion

Insertion is the process of adding a new node to a binary tree. The goal is to ensure that the tree remains balanced and maintains all the properties of a binary tree.

To insert a new node into a binary tree, we follow these steps: 1. If the tree is empty, create a new node and set it as the root. 2. If the tree is not empty, start from the root and compare the value to be inserted with the current node's value. 3. If the value is less than the current node's value, move to the left subtree and repeat step 2. 4. If the value is greater than the current node's value, move to the right subtree and repeat step 2. 5. If both subtrees are empty, create a new node and insert it as either the left or right child of the current node based on the comparison.

Here's an example implementation of inserting nodes into a binary tree in Java: java {code}

In this example, the insert method takes the value to be inserted as a parameter. It calls the insertRec method recursively to perform the actual insertion. The insertRec method follows the steps mentioned earlier to insert the new node into the correct position in the tree.

After inserting the nodes into the binary tree, we can perform an inorder traversal to verify that the nodes are inserted properly. The inorder method traverses the tree in inorder (left-root-right) and prints the key values of the nodes.

To test the insertion functionality, the example code creates a binary tree and inserts the values 50, 30, 20, 40, 70, 60, 80 in that order. Finally, it performs an inorder traversal and displays the key values of the nodes.

Now you have an understanding of how to insert nodes into a binary tree! In the next lesson, we will explore the process of deleting nodes from a binary tree.

```java
public class Main {
    static class Node {
        int key;
        Node left, right;

        public Node(int item) {
            key = item;
            left = right = null;
        }
    }

    static Node root;

    void insert(int key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }

        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);

        return root;
    }

    void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.key + " ");
            inorder(root.right);
        }
    }

    public static void main(String[] args) {
        Main tree = new Main();

        /* Inserting nodes into the binary tree */
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        /* Displaying the inorder traversal of the binary tree */
        tree.inorder(root);
    }
}
```

To insert a new node into a binary tree, we follow these steps: 1. If the tree is empty, create a new node and set it as the root. 2. If the tree is not empty, start from the root and compare the value to be inserted with the current node's value. 3. If the value is less than the current node's value, move to the left subtree and repeat step 2. 4. If the value is greater than the current node's value, move to the right subtree and repeat step 2. 5. If both subtrees are empty, create a new node and insert it as either the left or right child of the current node based on the comparison.

To insert the value 8 into the binary tree shown below, we would follow these steps: 10 / \ 5 15 / \ / 3 7 12 / \ 11 13

Step 1: Start from the root (10) and compare 8 with 10. Step 2: Since 8 is less than 10, move to the left subtree. Step 3: Compare 8 with 5. Step 4: Since 8 is greater than 5, move to the right subtree. Step 5: Compare 8 with 7. Step 6: Since 8 is greater than 7 and the right subtree is empty, insert 8 as the right child of 7.

Conclusion: The value 8 would be inserted as the right child of the node with the value 7.

Fill in the blank: The value 8 would be inserted as the _______________ child of the node with the value 7.

Deletion

Deletion is the process of removing a node from a binary tree. When deleting a node, it is important to maintain the properties and structure of the binary tree.

To delete a node from a binary tree, we follow these steps:

1. If the tree is empty, return null.
2. If the node to be deleted is a leaf node (has no children), simply remove the node.
3. If the node to be deleted has only one child, replace the node with its child.
4. If the node to be deleted has two children, find the inorder successor (the node with the smallest key value in the right subtree) and replace the node to be deleted with the inorder successor. Then, recursively delete the inorder successor from the right subtree.

Here is an example implementation of deleting a node from a binary tree in Java: java {code}

In this example, the deleteNode method takes the root of the binary tree and the key value of the node to be deleted as parameters. It recursively searches for the node to be deleted and performs the deletion based on the three cases mentioned above.

To test the deletion functionality, the example code creates a binary tree and deletes the node with the key value 50. After deleting the node, it performs an inorder traversal and displays the key values of the nodes to verify that the node has been successfully deleted.

Deleting nodes from a binary tree can be a complex operation, particularly when dealing with nodes that have two children. It requires careful consideration of various cases and the rearrangement of the tree structure. Understanding the deletion process is fundamental in effectively managing and manipulating binary trees.

```java
class Main {
  public static void main(String[] args) {
    // replace with your Java logic here
    // Sample code for deleting a node from a binary tree
    // Assume we have a BinaryTreeNode class with properties: key, left, right
    BinaryTreeNode root = createBinaryTree();
    int keyToDelete = 50;
    root = deleteNode(root, keyToDelete);
    System.out.println("After deleting node with key " + keyToDelete + ":");
    inorder(root);
  }

  public static BinaryTreeNode deleteNode(BinaryTreeNode root, int key) {
    if (root == null)
      return root;

    if (key < root.key)
      root.left = deleteNode(root.left, key);
    else if (key > root.key)
      root.right = deleteNode(root.right, key);
    else {
      if (root.left == null)
        return root.right;
      else if (root.right == null)
        return root.left;

      root.key = minValue(root.right);

      root.right = deleteNode(root.right, root.key);
    }
    return root;
  }

  public static int minValue(BinaryTreeNode node) {
    int minValue = node.key;
    while (node.left != null) {
      minValue = node.left.key;
      node = node.left;
    }
    return minValue;
  }

  public static void inorder(BinaryTreeNode root) {
    if (root != null) {
      inorder(root.left);
      System.out.println(root.key);
      inorder(root.right);
    }
  }

  public static BinaryTreeNode createBinaryTree() {
    BinaryTreeNode root = new BinaryTreeNode(50);
    root.left = new BinaryTreeNode(30);
    root.right = new BinaryTreeNode(70);
    root.left.left = new BinaryTreeNode(20);
    root.left.right = new BinaryTreeNode(40);
    root.right.left = new BinaryTreeNode(60);
    root.right.right = new BinaryTreeNode(80);
    return root;
  }

  static class BinaryTreeNode {
    int key;
    BinaryTreeNode left;
    BinaryTreeNode right;

    public BinaryTreeNode(int item) {
      key = item;
      left = right = null;
    }
  }
}

```

Deletion is the process of removing a node from a binary tree.

Searching

Searching is a fundamental operation when working with binary trees. It involves finding a specific key value within the binary tree. There are various searching techniques that can be used, depending on the requirements and characteristics of the binary tree.

One commonly used searching technique is the inorder traversal. In inorder traversal, the left subtree is traversed first, followed by the root node, and then the right subtree. This results in visiting the nodes in ascending order of key values.

Here is an example of performing an inorder traversal of a binary tree in Java:

  class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class BinarySearchTree {
    TreeNode root;

    void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        inorderTraversal(node.left);
        System.out.print(node.val + " ");
        inorderTraversal(node.right);
    }
}

Which traversal technique is commonly used for searching in binary trees?

Traversal

Traversal is the process of visiting and examining all nodes in a binary tree in a specific order. There are three commonly used traversal methods: inorder traversal, preorder traversal, and postorder traversal.

• Inorder Traversal: In inorder traversal, the left subtree is visited first, then the root node, and finally the right subtree. The inorder traversal visits the nodes in ascending order of their keys.

• Preorder Traversal: In preorder traversal, the root node is visited first, followed by the left subtree, and then the right subtree.

• Postorder Traversal: In postorder traversal, the left subtree is visited first, then the right subtree, and finally the root node.

Here is an example of performing these traversal methods on a binary tree in Java:

import java.util.LinkedList;

public class TraversalExample {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        // Create a binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // Perform inorder traversal
        System.out.println("Inorder Traversal:");
        inorderTraversal(root);

        // Perform preorder traversal
        System.out.println("Preorder Traversal:");
        preorderTraversal(root);

        // Perform postorder traversal
        System.out.println("Postorder Traversal:");
        postorderTraversal(root);
    }

    // Inorder Traversal
    static void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        inorderTraversal(node.left);
        System.out.print(node.val + " ");
        inorderTraversal(node.right);
    }

    // Preorder Traversal
    static void preorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        System.out.print(node.val + " ");
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    // Postorder Traversal
    static void postorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.print(node.val + " ");
    }
}

```java
import java.util.LinkedList;

public class TraversalExample {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        // Create a binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // Perform inorder traversal
        System.out.println("Inorder Traversal:");
        inorderTraversal(root);

        // Perform preorder traversal
        System.out.println("Preorder Traversal:");
        preorderTraversal(root);

        // Perform postorder traversal
        System.out.println("Postorder Traversal:");
        postorderTraversal(root);
    }

    // Inorder Traversal
    static void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        inorderTraversal(node.left);
        System.out.print(node.val + " ");
        inorderTraversal(node.right);
    }

    // Preorder Traversal
    static void preorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        System.out.print(node.val + " ");
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    // Postorder Traversal
    static void postorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }

        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.print(node.val + " ");
    }
}
```

In ___________ traversal, the left subtree is visited first, then the root node, and finally the right subtree.

Putting It Together

Congratulations! You have finished the tutorial on binary trees. You have learned how binary trees are structured and how to perform various operations on them such as insertion, deletion, searching, and traversal.

By now, you should have a clear understanding of the concepts and principles behind binary trees. You have seen how they can be used to solve various problems and implement different data structures.

In this tutorial, we have covered the following topics:

• Introduction to Binary Trees
• Binary Search Trees
• AVL Trees
• Red-Black Trees
• Insertion
• Deletion
• Searching
• Traversal

With this knowledge, you are well-equipped to tackle more complex data structures and algorithms. The concepts you have learned can be applied to a wide range of problems and scenarios.

Remember, practice makes perfect. Try implementing binary trees in different programming languages or explore more advanced topics like self-balancing trees or thread-safe binary trees.

Keep in mind the design patterns and architecture principles you have learned throughout your career. Just like an architect designs a building with different components and systems, you can design software using binary trees as part of a larger architecture.

As a senior engineer with a strong coding background, you have the skills to break down complex problems and apply your knowledge of data structures and algorithms to drive elegant and efficient solutions.

Now, it's time to take your understanding of binary trees to the next level. Are you ready for the challenge?

```java
class Main {
  public static void main(String[] args) {
    // Here are some examples of using the binary tree methods

    // Create a binary tree
    BinaryTree tree = new BinaryTree();

    // Insert nodes
    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(2);
    tree.insert(4);
    tree.insert(6);
    tree.insert(8);

    // Print the tree
    System.out.println("Binary Tree:");
    tree.print();

    // Search for a node
    int key = 6;
    TreeNode node = tree.search(key);
    if (node != null) {
      System.out.println("Node with key " + key + " found");
    } else {
      System.out.println("Node with key " + key + " not found");
    }
  }
}

// Implementation of a Binary Tree
class BinaryTree {

  // TreeNode class
  static class TreeNode {
    int key;
    TreeNode left;
    TreeNode right;

    TreeNode(int key) {
      this.key = key;
      left = right = null;
    }
  }

  // Root of Binary Tree
  TreeNode root;

  // Constructor
  BinaryTree() {
    root = null;
  }

  // Insert a node
  void insert(int key) {
    root = insertRec(root, key);
  }

  // Recursive function to insert a key in the tree
  TreeNode insertRec(TreeNode root, int key) {
    // If the tree is empty, return a new node
    if (root == null) {
      root = new TreeNode(key);
      return root;
    }

    // Otherwise, recur down the tree
    if (key < root.key)
      root.left = insertRec(root.left, key);
    else if (key > root.key)
      root.right = insertRec(root.right, key);

    // Return the (unchanged) node pointer
    return root;
  }

  // Search for a node
  TreeNode search(int key) {
    return searchRec(root, key);
  }

  // Recursive function to search for a key in a tree
  TreeNode searchRec(TreeNode root, int key) {
    // Base Cases: root is null or key is present at root
    if (root == null || root.key == key)
      return root;

    // Key is greater than root's key
    if (root.key < key)
      return searchRec(root.right, key);

    // Key is smaller than root's key
    return searchRec(root.left, key);
  }

  // Print the tree
  void print() {
    printRec(root);
  }

  // Recursive function to print the tree
  void printRec(TreeNode node) {
    if (node != null) {
      printRec(node.left);
      System.out.println(node.key);
      printRec(node.right);
    }
  }
}
```

Binary trees are a type of data structure that store data in a hierarchical format.

Generating complete for this lesson!