1 2 Previous Next 17 Replies Latest reply: Mar 30, 2007 11:57 PM by 807606 Go to original post RSS
      • 15. Re: BST: Finding the second smallest item in the tree...
        807606
        Patterns, heh, everyone and their patterns. Meanwhile, the other guy already solved the problem. Just kidding, patterns are good, but they have their place.
        getSmallest(Node subtree, boolean second) {
            Node n = subtree;
            Node nParent = null;
            while (n.left != null) {
                nParent = n;
                n = n.left;
            }
            if (second) {
                if (n.right != null) // second smallest is smallest node in right subtree
                   return getSmallest(n.right, false);
                else if (nParent != null) // smallest node's parent is second smallest
                   return nParent.value;
            }
            // this happens when not finding second, or there's only 1 node in the tree
            return n.value;
        }
        • 16. Re: BST: Finding the second smallest item in the tree...
          807606
          Ah, I like this approach.

          It still requires I use it as an auxiliary method due to the signature change, but it's straightforward and simple.

          I'll have to try to adapt that a little, but it's really exactly what I was trying to get to.
          • 17. Re: BST: Finding the second smallest item in the tree...
            807606
            So, DigitalLimit, go what you were looking for yet?
            1 2 Previous Next