Tree Operations

In this section, we will discuss common operations on trees, such as insertion, deletion, and searching.

Insertion

To insert a value into a binary tree, we start at the root node and recursively traverse the tree until we find an empty location where the new value can be inserted. If the value is less than the current node's value, we go to the left subtree. If the value is greater than the current node's value, we go to the right subtree. Once we find an empty location, we create a new node and insert the value.

Here's the Java implementation of the insert method:

1public void insert(TreeNode root, int val) {
2    if (root == null) {
3        root = new TreeNode(val);
4    } else {
5        if (val < root.val) {
6            if (root.left == null) {
7                root.left = new TreeNode(val);
8            } else {
9                insert(root.left, val);
10            }
11        } else {
12            if (root.right == null) {
13                root.right = new TreeNode(val);
14            } else {
15                insert(root.right, val);
16            }
17        }
18    }
19}

Searching

To search for a value in a binary tree, we start at the root node and recursively traverse the tree until we find the value we are looking for or reach a null node. If the value is equal to the current node's value, we return true. If the value is less than the current node's value, we search in the left subtree. If the value is greater than the current node's value, we search in the right subtree.

Here's the Java implementation of the search method:

1public boolean search(TreeNode root, int val) {
2    if (root == null) {
3        return false;
4    }
5
6    if (val == root.val) {
7        return true;
8    } else if (val < root.val) {
9        return search(root.left, val);
10    } else {
11        return search(root.right, val);
12    }
13}

Deletion

To delete a node from a binary tree, we first search for the node we want to delete. If the node is found, there are three cases to consider:

1. If the node has no children, we simply remove it from the tree.
2. If the node has one child, we replace the node with its child.
3. If the node has two children, we have to find the minimum value in the right subtree (or the maximum value in the left subtree) and replace the node's value with that value. Then, we recursively delete the node with the replaced value.

Here's the Java implementation of the delete method:

1public TreeNode delete(TreeNode root, int val) {
2    if (root == null) {
3        return null;
4    }
5
6    if (val < root.val) {
7        root.left = delete(root.left, val);
8    } else if (val > root.val) {
9        root.right = delete(root.right, val);
10    } else {
11        if (root.left == null) {
12            return root.right;
13        } else if (root.right == null) {
14            return root.left;
15        }
16
17        root.val = findMin(root.right);
18        root.right = delete(root.right, root.val);
19    }
20
21    return root;
22}

xxxxxxxxxx

}

import java.util.*;

​

public class TreeNode {

    int val;

    TreeNode left;

    TreeNode right;

​

    public TreeNode(int val) {

        this.val = val;

        this.left = null;

        this.right = null;

    }

}

​

public class TreeOperations {

    // Insertion

    public void insert(TreeNode root, int val) {

        if (root == null) {

            root = new TreeNode(val);

        } else {

            if (val < root.val) {

                if (root.left == null) {

                    root.left = new TreeNode(val);

                } else {

                    insert(root.left, val);

                }

            } else {

                if (root.right == null) {

                    root.right = new TreeNode(val);