C Program 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.

[pastacode lang=”c” manual=”%23include%20%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20A%20binary%20tree%20node%20has%20data%2C%20pointer%20to%20left%20child%20%0A%20%20%20and%20a%20pointer%20to%20right%20child%20*%2F%0Astruct%20node%20%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20left%3B%0A%20%20%20%20struct%20node*%20right%3B%0A%7D%3B%0A%20%0A%2F*%20Helper%20function%20that%20allocates%20a%20new%20node%20%0Awith%20the%20given%20data%20and%20NULL%20left%20and%20right%20%0Apointers.%20*%2F%0Astruct%20node*%20newNode(int%20data)%20%0A%7B%0A%20%20struct%20node*%20node%20%3D%20(struct%20node*)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20malloc(sizeof(struct%20node))%3B%0A%20%20node-%3Edata%20%20%3D%20data%3B%0A%20%20node-%3Eleft%20%20%3D%20NULL%3B%0A%20%20node-%3Eright%20%3D%20NULL%3B%0A%20%20%20%0A%20%20return(node)%3B%0A%7D%0A%20%0A%2F*%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*%2F%0Astruct%20node*%20insert(struct%20node*%20node%2C%20int%20data)%20%0A%7B%0A%20%20%2F*%201.%20If%20the%20tree%20is%20empty%2C%20return%20a%20new%2C%20%20%20%20%20%0A%20%20%20%20%20%20single%20node%20*%2F%0A%20%20if%20(node%20%3D%3D%20NULL)%20%0A%20%20%20%20return(newNode(data))%3B%20%20%0A%20%20else%0A%20%20%7B%0A%20%20%20%20%2F*%202.%20Otherwise%2C%20recur%20down%20the%20tree%20*%2F%0A%20%20%20%20if%20(data%20%3C%3D%20node-%3Edata)%20%0A%20%20%20%20%20%20%20%20node-%3Eleft%20%20%3D%20insert(node-%3Eleft%2C%20data)%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20node-%3Eright%20%3D%20insert(node-%3Eright%2C%20data)%3B%0A%20%20%20%0A%20%20%20%20%2F*%20return%20the%20(unchanged)%20node%20pointer%20*%2F%0A%20%20%20%20return%20node%3B%20%0A%20%20%7D%0A%7D%0A%20%0A%2F*%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*%2F%0Aint%20minValue(struct%20node*%20node)%20%7B%0A%20%20struct%20node*%20current%20%3D%20node%3B%0A%20%0A%20%20%2F*%20loop%20down%20to%20find%20the%20leftmost%20leaf%20*%2F%0A%20%20while%20(current-%3Eleft%20!%3D%20NULL)%20%7B%0A%20%20%20%20current%20%3D%20current-%3Eleft%3B%0A%20%20%7D%0A%20%20return(current-%3Edata)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20sameTree%20function*%2F%20%20%20%0Aint%20main()%0A%7B%0A%20%20struct%20node*%20root%20%3D%20NULL%3B%0A%20%20root%20%3D%20insert(root%2C%204)%3B%0A%20%20insert(root%2C%202)%3B%0A%20%20insert(root%2C%201)%3B%0A%20%20insert(root%2C%203)%3B%0A%20%20insert(root%2C%206)%3B%0A%20%20insert(root%2C%205)%3B%20%20%0A%20%0A%20%20printf(%22%5Cn%20Minimum%20value%20in%20BST%20is%20%25d%22%2C%20minValue(root))%3B%0A%20%20getchar()%3B%0A%20%20return%200%3B%20%20%20%20%0A%7D” message=”C Programming” highlight=”” provider=”manual”/]

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.

[ad type=”banner”]