Search an element in a binary tree. Simple Java example.

How to search an element in a binary tree in Java? This problem is one of the fundamental issues in any technical interview. Here, the basic logic is almost the same as inserting the element in the binary tree. To find an element that value less than the root value, we are going on the binary tree’s left side. Suppose the value is more than the root element we are going on the tree’s right side. To make it happen, we should write a function based on the recursion. We are repeating this logic until we find the right node or the last checked node will be null.

A critical thing you should keep in mind.

While we are going through the recursion, we have to keep in mind the call stack. It would help if you understood how the program is running the code during recursion.

An example of how to search for an element in a binary tree? The detailed solution in Java.

If you implemented the binary tree in a sorted way and want to find the element, you should follow the next steps: 

• It would be best if you used recursion. There is no looping for that solution;
• Check if the node equals null. That “if” condition is pointing that there is no value that we need. As a result, we return false. We need to make this check at the beginning of the function to avoid null pointer in future checks;

            if (node == null){
                return false;
            }

• Check if the searched value is equal to the current node’s value. Only in this case, we return true if the program jumps inside this “if” condition. That means we have found the node; 

            if (node.data == value){
                return true;
            }

• If the first and the second “if” conditions returned false, we are coming to the next “if” condition. If we are here, that means need to make one more recursive call. That’s why we can check it’s value. If the new node’s value is less than the current node’s value, we should recursively rerun the function. As we move our running to the left side of the tree;

                if (value < node.data){
                return searchRecursive(node.left, value);

• Otherwise, the searched element’s value is more than the value of the current element’s value. That means we should run to the right side. Just make another recursion call, and as a parameter, we should pass the right node of the current node and the value of the new node; 

            } else {
                return searchRecursive(node.right, value);
            }

As a result, that function will run itself until it will find the needed value or will stop by the null node reference.

Animated:

Step-by-step schema:

Full code:

private boolean searchRecursive(TreeNode node, int value){
            //If null - means there is no such value in a tree
            if (node == null){
                return false;
            }

            //If data is equals - means we have found needed value
            if (node.data == value){
                return true;
            }

            //Moving on the left side of the tree
            if (value < node.data){
                return searchRecursive(node.left, value);
            } else {
                //Moving on the right side of the tree
                return searchRecursive(node.right, value);
            }
        }

Full code and more examples in my facebook group.

Useful links:

• Implementation of the binary tree
• Pre-order traversal example
• In order traversal sample
• Post-order traversal Java example
• Insert an element in a binary tree