Binary search tree

Stanislav Gumeniuk included in Computer Science

2020.05.24 165 words One minute

Contents

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


/**
 * 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)
}