{"id":26969,"date":"2018-01-02T20:35:49","date_gmt":"2018-01-02T15:05:49","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26969"},"modified":"2018-01-02T20:35:49","modified_gmt":"2018-01-02T15:05:49","slug":"java-program-find-node-minimum-value-binary-search-tree","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-program-find-node-minimum-value-binary-search-tree\/","title":{"rendered":"Java Program Find the node with minimum value in a Binary Search Tree"},"content":{"rendered":"<p>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.<\/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<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Java Programming<\/span> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\">\/\/ Java program to find minimum value node in Binary Search Tree<br\/> <br\/>\/\/ A binary tree node<br\/>class Node {<br\/> <br\/>    int data;<br\/>    Node left, right;<br\/> <br\/>    Node(int d) {<br\/>        data = d;<br\/>        left = right = null;<br\/>    }<br\/>}<br\/> <br\/>class BinaryTree {<br\/> <br\/>    static Node head;<br\/>     <br\/>    \/* Given a binary search tree and a number, <br\/>     inserts a new node with the given number in <br\/>     the correct place in the tree. Returns the new <br\/>     root pointer which the caller should then use <br\/>     (the standard trick to avoid using reference <br\/>     parameters). *\/<br\/>    Node insert(Node node, int data) {<br\/>         <br\/>        \/* 1. If the tree is empty, return a new,     <br\/>         single node *\/<br\/>        if (node == null) {<br\/>            return (new Node(data));<br\/>        } else {<br\/>             <br\/>            \/* 2. Otherwise, recur down the tree *\/<br\/>            if (data &lt;= node.data) {<br\/>                node.left = insert(node.left, data);<br\/>            } else {<br\/>                node.right = insert(node.right, data);<br\/>            }<br\/> <br\/>            \/* return the (unchanged) node pointer *\/<br\/>            return node;<br\/>        }<br\/>    }<br\/> <br\/>    \/* Given a non-empty binary search tree,  <br\/>     return the minimum data value found in that <br\/>     tree. Note that the entire tree does not need <br\/>     to be searched. *\/<br\/>    int minvalue(Node node) {<br\/>        Node current = node;<br\/> <br\/>        \/* loop down to find the leftmost leaf *\/<br\/>        while (current.left != null) {<br\/>            current = current.left;<br\/>        }<br\/>        return (current.data);<br\/>    }<br\/>     <br\/>    \/\/ Driver program to test above functions<br\/>    public static void main(String[] args) {<br\/>        BinaryTree tree = new BinaryTree();<br\/>        Node root = null;<br\/>        root = tree.insert(root, 4);<br\/>        tree.insert(root, 2);<br\/>        tree.insert(root, 1);<br\/>        tree.insert(root, 3);<br\/>        tree.insert(root, 6);<br\/>        tree.insert(root, 5);<br\/> <br\/>        System.out.println(&quot;The minimum value of BST is &quot; + tree.minvalue(root));<br\/>    }<br\/>}<br\/> <br\/>\/\/ This code has been contributed by Mayank Jaiswal<\/code><\/pre> <\/div>\n<p><strong>Time Complexity:<\/strong> O(n) Worst case happens for left skewed trees.<br \/>\nSimilarly we can get the maximum value by recursively traversing the right node of a binary search tree.<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Java 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":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80126,1,2139],"tags":[80551,80554,80548,80569,80571,80570,80543,80572,70290,80565,71255,80574,80544,80541,70280,80560],"class_list":["post-26969","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree","category-coding","category-java","tag-binary-search-tree-traversal-inorder-preorder-postorder-example","tag-define-bst","tag-definition-of-binary-search-tree","tag-find-max-value-in-binary-tree-java","tag-find-maximum-in-binary-search-tree","tag-find-minimum-value-in-binary-tree-java","tag-how-to-construct-a-binary-tree","tag-isbst","tag-java-program-for-binary-search","tag-min-search","tag-min-tree","tag-program-of-binary-search-tree","tag-properties-of-binary-tree-in-data-structure","tag-root-binary","tag-search-tree","tag-write-an-algorithm-for-binary-search-with-example"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26969","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=26969"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26969\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26969"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26969"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26969"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}