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:

1{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.

xxxxxxxxxx

}

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;