Find the node with minimum value in a Binary Search Tree
This is quite simple. Just traverse the node from root to left recursively until left is NULL. The node whose left is NULL is the node with minimum value.
For the above tree, we start with 20, then we move left 8, we keep on moving to left until we see NULL. Since left of 4 is NULL, 4 is the node with minimum value.
Implementation of Python Programming:
[pastacode lang=”python” manual=”%23%20Python%20program%20to%20find%20the%20node%20with%20minimum%20value%20in%20bst%0A%20%0A%23%20A%20binary%20tree%20node%0Aclass%20Node%3A%0A%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20key)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20key%0A%20%20%20%20%20%20%20%20self.left%20%3D%20None%0A%20%20%20%20%20%20%20%20self.right%20%3D%20None%0A%20%0A%22%22%22%20Give%20a%20binary%20search%20tree%20and%20a%20number%2C%20%0Ainserts%20a%20new%20node%20with%20the%20given%20number%20in%20%0Athe%20correct%20place%20in%20the%20tree.%20Returns%20the%20new%20%0Aroot%20pointer%20which%20the%20caller%20should%20then%20use%20%0A(the%20standard%20trick%20to%20avoid%20using%20reference%20%0Aparameters).%20%22%22%22%0Adef%20insert(node%2C%20data)%3A%0A%20%0A%20%20%20%20%23%201.%20If%20the%20tree%20is%20empty%2C%20return%20a%20new%2C%0A%20%20%20%20%23%20single%20node%0A%20%20%20%20if%20node%20is%20None%3A%0A%20%20%20%20%20%20%20%20return%20(Node(data))%0A%20%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%23%202.%20Otherwise%2C%20recur%20down%20the%20tree%0A%20%20%20%20%20%20%20%20if%20data%20%3C%3D%20node.data%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20node.left%20%3D%20insert(node.left%2C%20data)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20node.right%20%3D%20insert(node.right%2C%20data)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Return%20the%20(unchanged)%20node%20pointer%0A%20%20%20%20%20%20%20%20return%20node%0A%20%0A%22%22%22%20Given%20a%20non-empty%20binary%20search%20tree%2C%20%20%0Areturn%20the%20minimum%20data%20value%20found%20in%20that%20%0Atree.%20Note%20that%20the%20entire%20tree%20does%20not%20need%20%0Ato%20be%20searched.%20%22%22%22%0Adef%20minValue(node)%3A%0A%20%20%20%20current%20%3D%20node%0A%20%0A%20%20%20%20%23%20loop%20down%20to%20find%20the%20lefmost%20leaf%0A%20%20%20%20while(current.left%20is%20not%20None)%3A%0A%20%20%20%20%20%20%20%20current%20%3D%20current.left%0A%20%0A%20%20%20%20return%20current.data%0A%20%0A%23%20Driver%20program%0Aroot%20%3D%20None%0Aroot%20%3D%20insert(root%2C4)%0Ainsert(root%2C2)%0Ainsert(root%2C1)%0Ainsert(root%2C3)%0Ainsert(root%2C6)%0Ainsert(root%2C5)%0A%20%0Aprint%20%22%5CnMinimum%20value%20in%20BST%20is%20%25d%22%20%20%25(minValue(root))%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Nikhil%20Kumar%20Singh(nickzuck_007)” message=”Python Programming” highlight=”” provider=”manual”/]Output:
Minimum value in BST is 1
Time Complexity: O(n) Worst case happens for left skewed trees.
Similarly we can get the maximum value by recursively traversing the right node of a binary search tree.