This is the ninth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Hello, everyone, today is the 9th day I participated in the August more text, today brings you about the binary tree related algorithm problem is the binary search tree search, the text is as follows:

Topic:

Given the root node of a binary search tree (BST) and a value. You need to find a node in the BST whose node value is equal to the given value. Returns a subtree with this node as the root. Returns NULL if the node does not exist.

Such as:

You should return as the subtree:

In the example above, if the value we are looking for is 5, but there is no node with a value of 5, we should return NULL.

Their thinking

The recursive implementation is very simple:

  • If the root node is null root == NULL or the value of the root node is equal to the search value val == root.val, return the root node.

  • If val < root.val, go to the left subtree of the root node and look for searchBST(root.left, val).

  • If val > root.val, go to the right subtree of the root node and look for searchBST(root.right, val).

  • Returns the root node.

Code implementation

/** * Definition for a binary tree node. * public 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; *} *} */ class Solution {public TreeNode searchBST(TreeNode root, int val) { Continuous recursive search on both sides of the if (root = = null | | root. Val = = val) return the root; return val < root.val? searchBST(root.left, val) : searchBST(root.right, val); }}Copy the code

The last

Complexity analysis

  • Time complexity: O(h), where H is tree height. The average time complexity is O(logN), and the worst time complexity is O(N).

  • Space complexity: O(h), depth of recursion stack is h. The depth is O(logN) in the average case and O(N) in the worst case.