{"id":26970,"date":"2018-01-02T21:37:35","date_gmt":"2018-01-02T16:07:35","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26970"},"modified":"2018-10-31T10:27:13","modified_gmt":"2018-10-31T04:57:13","slug":"python-program-find-node-minimum-value-binary-search-tree","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-program-find-node-minimum-value-binary-search-tree\/","title":{"rendered":"Find the node with minimum value in a Binary Search Tree"},"content":{"rendered":"<p><span style=\"color: #000080;\"><strong>Find the node with minimum value in a Binary Search Tree<\/strong><\/span><\/p>\n<p>This is quite simple. Just <a href=\"https:\/\/www.wikitechy.com\/technology\/python-program-inorder-tree-traversal-without-recursion-without-stack\/\" target=\"_blank\" rel=\"noopener\">traverse<\/a> the node from root to left <a href=\"https:\/\/www.wikitechy.com\/technology\/python-algorithm-find-length-linked-list-iterative-recursive\/\" target=\"_blank\" rel=\"noopener\">recursively<\/a> until left is NULL. The node whose left is NULL is the node with minimum value.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter  wp-image-31754\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2018\/01\/bst-tree.png\" alt=\"minimum value in binary search tree\" width=\"295\" height=\"248\" \/><\/p>\n<p>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.<\/p>\n<h3 id=\"implementation-of-python-programming\"><span style=\"color: #003300;\"><strong>Implementation of Python Programming:<\/strong><\/span><\/h3>\n[pastacode lang=\u201dpython\u201d manual=\u201d%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)\u201d message=\u201dPython Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output\"><span style=\"color: #008000;\">Output:<\/span><\/h3>\n<pre>Minimum value in BST is 1<\/pre>\n<p><span style=\"color: #008080;\"><strong>Time Complexity:<\/strong> <\/span><strong>O(n)<\/strong> Worst case happens for left skewed <a href=\"https:\/\/www.wikitechy.com\/technology\/python-program-inorder-successor-binary-search-tree\/\" target=\"_blank\" rel=\"noopener\">trees<\/a>.<br \/>\nSimilarly we can get the maximum value by recursively traversing the right node of a <a href=\"https:\/\/www.wikitechy.com\/technology\/python-program-check-binary-tree-bst-not\/\" target=\"_blank\" rel=\"noopener\">binary search tree<\/a>.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Python Program &#8211; Find the node with minimum value in a Binary Search Tree &#8211; Just traverse the node from root to left recursively until left is NULL.<\/p>\n","protected":false},"author":1,"featured_media":28089,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,83517],"tags":[70276,80566,80538,70264,80567,70268,80548,80543,70290,80565,80544,80738,80737,80541,80560],"class_list":["post-26970","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coding","category-python-programming","tag-algorithm-for-binary-search","tag-algorithm-for-create-binary-tree","tag-algorithm-of-binary-search-tree","tag-binary-search-algorithm","tag-binary-search-trees-ppt","tag-binary-tree","tag-definition-of-binary-search-tree","tag-how-to-construct-a-binary-tree","tag-java-program-for-binary-search","tag-min-search","tag-properties-of-binary-tree-in-data-structure","tag-python-binary-search-tree","tag-python-bst-implementation","tag-root-binary","tag-write-an-algorithm-for-binary-search-with-example"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26970","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26970"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26970\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/28089"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26970"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26970"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26970"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}