Search in a Binary Search Tree

Find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such a node doesn't exist, you should return NULL.

Example:

Input:
        4
       / \
      2   7
     / \
    1   3

val= 2 

  Output:    2     
            / \   
           1   3

Inorder: 1 2 3

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SearchInBinarySearchTree {
    static List<Integer> result = new ArrayList<>();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        int val = 2;
        TreeNode find = searchBST(root, val);
        inorder(find);
        System.out.println("Tree Inorder is " + Arrays.asList(result));
    }

    // function to search the
    // value in tree and return
    // the subtree in which it exist
    private static TreeNode searchBST(TreeNode root, int val) {
        // if tree is empty
        if (root == null)
            return null;
        // if root data is same as target value
        if (root.val == val)
            return root;
        // it root data is greater than
        // target value then call for left subtree
        if (root.val > val)
            return searchBST(root.left, val);

        // else call for right subtree
        return searchBST(root.right, val);
    }

    public static void inorder(TreeNode root) {
        if (root == null)
            return;

        // visit left node
        inorder(root.left);
        // Add root value
        result.add(root.val);
        // visit right node
        inorder(root.right);

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

    TreeNode() {
    }

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

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode()
    {

    }
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};

//function to seach the
//value in tree and return
//the subtree in which it exist
TreeNode *searchBST(TreeNode* root, int val) 
{
       //if tree is empty
        if(root==NULL)
              return NULL;
        //if root data is same as target value
        if(root->data==val)
              return root;
        //it root data is greater than
        //target value then call for left subtree
        if(root->data>val)
              return searchBST(root->left,val);

        //else call for right subtree
        return searchBST(root->right,val);
}
//Function to find inorder Traversal
//of tree
void inorderTraversal(TreeNode *root)
{
    //Base Case
    if(root==NULL)
       return;
    //visit left subtree
    inorderTraversal(root->left);
    // visit root
    cout<<root->data<<" ";
    //visit right subtree
    inorderTraversal(root->right);
}
int main()
{
    TreeNode *root=new TreeNode(4);
    root->left=new TreeNode(2);
    root->right=new TreeNode(7);
    root->left->left=new TreeNode(1);
    root->left->right=new TreeNode(3);
    int val=2;
    TreeNode *find=searchBST(root,val);
    inorderTraversal(find);
    return 0;

}