What is leftmost & rightmost node of a binary subtree?

Question

I was reading on this and in one place it says

The rightmost node will be the node with the greatest value in the left subtree which I assume then that the leftmost is the greatest value in the right subtree.

However, in another article it shows me a different approach to find the leftmost node:

1) If the given node has no right child :

Go to the root of the given node until it is the left child of any node. That node will be the next higher node in the tree.

2) If the given node has right child :

a) If the right child of the given node has no left child

The right child will be the next higher node.

b) If the right child of the given node has left child

The leftmost leaf node will be the next higher node.

i.e 2nd approach doesn't return greatest value as the 1st approach suggests Please clarify..

Answer 1

Judging by the link you attached, I assume you are specifically talking about binary SEARCH trees, which have rules about the make-up of their nodes.

As a general rule for binary trees (and by extension, subtrees):

• Every child to the right of a node will be greater than the node.
• Every child to the left of a node will be smaller than the node.

Thus, the right-most child of any given sub-tree will always be the highest value. Also, the left-most child of any given sub-tree will always be the lowest value.

Keep in mind that binary trees are slightly different from binary search trees, and these rules do not necessarily apply to binary trees.

Let's use the following binary search tree as an example:

        9
      /   \
     4     13
   /  \   /  \
  1   5  11  16

Suppose we are trying to look for the highest node value in the tree. If we start at node 9 (the "root"), we keep traversing down each right child of the node until there are no more right children (i.e. Start at Node 9, then move down to Node 13, and then end off Node 16). Therefore, 16 is the highest value in the tree.

Similarly with searching for the lowest node value in the tree, we start at the root node of our tree and keep traversing down each left child until no more left children exist.

Source: Learned this in my Data Structures and Algorithms course in university (IT student)

Hope this helps, and please feel free to correct any mistakes I may have made (I'm new here).

Answer 2

The idea is to use Level Order Traversal. To find first node, we use a variable isFirst. To separate levels, we enqueue NULL after every level. So in level order traversal, if we see a NULL, we know next node would be first node of its level and therefore we set isFirst.

void printCorner(Node *root)
{
    queue<Node *> q;
    q.push(root);
    q.push(NULL);
    bool isFirst=false;
    bool isOne = false;
    int last;
    Node *temp;
    while(!q.empty()){
        temp = q.front();
        q.pop();
        if(isFirst){
            cout<<temp->key<<" ";
            if(temp->left)q.push(temp->left);
            if(temp->right)q.push(temp->right);
            isFirst = false;
            isOne = true;
        }
        else if(temp==NULL){
            if(q.size()>=1)q.push(NULL);
            isFirst = true;
            if(!isOne)cout<<last<<" ";
        }
        else{
            last = temp->key;
            isOne = false;
            if(temp->left)q.push(temp->left);
            if(temp->right)q.push(temp->right);
        }
    }
}