Binary search tree question

[bleedi]

Hey, I was just wondering about searching a binary tree for the smallest / the largest value. Normally, the smallest is found by following the left branch until the last leaf is found. But what if we have a non-optimizing tree like this (8 being the root):

8 - 10 - 11
| |
| 1
|
6 - 7 - 9
| |
5 4

The smallest is "1", which can be found going first right and then left from the root, and the value found by "normal" method is "5". I know this might be a silly question, but shouldn't we always check all the branches and leaves when trying to find the smallest or the largest value in BST which isn't balanced? :)

EDIT:
Ehm... the ASCII tree doesn't show up quite right. Just copy it to notepad etc. to see it right.

[mrnutty]

Post the ascii art one more time, but this time wrap it under code tags. It looks like your binary search tree does not satisfy the property that all left subtree are smaller than the parent, and all right subtree are greater than the parent.

[griswolf]

We must clearly distinguish binary tree in which there is no particular order and binary search tree in which and a depth-first right to left traversal gives a fully sorted list. @bleedi used 'search' in the title, but not in the body. Same as @firstPerson, I'm not sure if the tree is merely unbalanced or just in non-sorted order.

• Assuming non-sorted order: You must visit every node, since there is no organizing order
• Assuming sorted but unbalanced: leftmost lowest node holds the 'smallest' item for some definition of 'smallest'

To see that even unbalanced, the rule holds, consider what happens when you insert unbalanced:

• If the item is the smallest, you will go left/small repeatedly until you have to create a node that is leftmost lowest.
• If the item is 'just barely larger than smallest', you will end up at the leftmost-lowest = smallest node, then add a new node on its right, so our smallest is still leftmost lowest.
• Adding anything larger than 'just barely' means the path branches right even earlier, so leftmost lowest is still smallest.
• It might be interesting to think about inserting unbalanced in (reverse) sorted order. The result is effectively a linked list with all the (right) left nodes empty. Here, it is obvious that the leftmost node is smallest.

[Momerath]

There are many ways to search a binary tree and we'll consider one here (Referred to as Left-Node-Right or LNR. There is also LRN, NLR, NRL, RLN, RNL. Half of those are just previous ones in reverse order).

method LNR(Node n) {
    if (n->left is not null) {
        LNR(n->left)
    }
    // do whatever you need to do on the current node, n (this is the N part of LNR)
    if (n->right is not null) {
        LNR(n->right)
    }
}

This is also known as a depth first search, since it looks at the bottom of the tree first before looking at the top nodes.