Binary search tree

Operations

Binary search trees should support 3 operations:

• insert element
• delete element
• find element

Find element

We have: tree Т and value K.

Problem: Check if exist node with value equal K – return this node.

Solution:

• If T is empty – return not found
• Check K with root node X.
  • If K==X – return this node
  • If K>X run recursion on right subtree of this node
  • If K<X run recursion on left subtree of this node

implementation:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return nil
    }
    
    if root.Val == val {
        return root
    }
    
    if root.Val > val {
        return searchBST(root.Left, val)
    }
    
    return searchBST(root.Right, val)
}