Basic BST Question From a New Programmer

Given the data set (8, 1, 6, 9, 3, 5, 4, 7) I drew the following binary search tree:

   8
  / \
  1  9
   \ 
    6
   / \ 
  3   7
   \ 
    5
   /
  4

My question is, if I wanted to remove the root node (8) from this tree, 开发者_Go百科how would I do it and what would the resulting tree-structure look like? Thank you very much for any help!

you will need to promote either a node from the left subtree or the right subtree. You can do this arbitrarily, or better still, promote from the deepest tree.

If promoting from the left sub tree, find the leaf by going right always starting in the left substree. Snip this leaf off the tree, and put it as the new root.

Likewise if promoting from the right sub tree, find the leaf by going left always starting in the right subtree. Snip this leaf off the tree, and put it as the new root.

            1
             \
              6
            /  \
           3    9 
            \  /
             5 7
            /
           4   

The tree will look as shown above. The best would be to reconstruct the tree again from scratch rather than having some logic to move the leaves and complicate the process.