Search the node with minimum value in a Binary search tree

Abhishek Kumar • Category: Data Structures • Tags: datastructures binary-search-tree

Search the node with minimum value in a binary search tree.
To search a node with a minimum value in a Binary Search Tree, we have to traverse to the left-most node at the bottom.

To search a node with minimum value in a Binary Search Tree (BST), we have to traverse to the left-most node at the bottom.

Because, in BST small element is always on the left side so minimum element will be location on the left-most at the bottom.

Example -

Input: 
      5
    /   \
   3     8
  / \   / \
 1   4 6   9


Output: 1

We can solve this problem in two ways-

Recursive solution
Iterative solution

Recursive solution

Algorithm

Find_Min(root)

1.  if root is null then return null
2.  if root.left is null then return root.data
3.  else return Find_Min(root.left)

class Node:
    def __init__(self, data):
        self.left = None
        self.data = data
        self.right = None

def find_min(root):
    if root is None:
        return None
    if root.left is None:
        return root.data
    else:
        return find_min(root.left)


bst_root = Node(10)
bst_root.left = Node(6)
bst_root.right = Node(16)
bst_root.left.left = Node(4)
bst_root.left.right = Node(9)
bst_root.right.left = Node(13)
bst_root.right.right = Node(20)
print(find_min(bst_root))

class Node {
  constructor(data) {
    this.left = null;
    this.data = data;
    this.right = null;
  }
}

function findMin(root) {
  if (root == null) {
    return null;
  }

  if (root.left == null) {
    return root.data;
  } else {
    return findMin(root.left);
  }
}

const bstRoot = new Node(10);
bstRoot.left = new Node(6);
bstRoot.right = new Node(16);
bstRoot.left.left = new Node(4);
bstRoot.left.right = new Node(9);
bstRoot.right.left = new Node(13);
bstRoot.right.right = new Node(20);
console.log(findMin(bstRoot));

Output

Iterative solution

Algorithm

Find_Iter(root)

1.  if root is null then return null
2.  node = root
3.  while node.left
4.      node = node.left
5.  return node.data

class Node:
    def __init__(self, data):
        self.left = None
        self.data = data
        self.right = None

def find_min(root):
    if root is None: return None
    node = root
    while node.left:
        node = node.left
    return node.data


bst_root = Node(10)
bst_root.left = Node(6)
bst_root.right = Node(16)
bst_root.left.left = Node(4)
bst_root.left.right = Node(9)
bst_root.right.left = Node(13)
bst_root.right.right = Node(20)
print(find_min(bst_root))

class Node {
  constructor(data) {
    this.left = null;
    this.data = data;
    this.right = null;
  }
}

function findMin(root) {
  if (root == null) {
    return null;
  }

  let node = root;
  while (node.left) {
    node = node.left;
  }
  return node.data;
}

const bstRoot = new Node(10);
bstRoot.left = new Node(6);
bstRoot.right = new Node(16);
bstRoot.left.left = new Node(4);
bstRoot.left.right = new Node(9);
bstRoot.right.left = new Node(13);
bstRoot.right.right = new Node(20);
console.log(findMin(bstRoot));

Output

Time complexity: The time complexity of both of these solution will be O(log n) if the tree is balanced but in worst case the time complete will be O(n) if the tree is not balanced i.e, tree becomes skewed.

Search a node in Binary search tree

AUTHOR

Abhishek Kumar

Search the node with minimum value in a Binary search tree

Example -

Recursive solution

Algorithm

Output

Iterative solution

Algorithm

Output

Abhishek Kumar

Recommended Posts -