unexpected binary tree result

Question

struct BSTreeNode
{
    struct BSTreeNode *leftchild;  
        AnsiString data;  
    struct BSTreeNode *rightchild;  
};

struct BSTreeNode * root;  

String tree = "";

struct BSTreeNode * newNode(AnsiString x)  
{
    struct BSTreeNode * node = new struct BSTreeNode;
    node->data = x; 
    node->leftchild = NULL;  
    node->rightchild = NULL;  
    return node;
}

struct BSTreeNode * insertBSTree(struct BSTreeNode * node , AnsiString x)  
{   if(node == NULL) return newNode(x);
    if(x < node->data)
        node->leftchild = insertBSTree(node->leftchild, x);
    else
        node->rightchild = insertBSTree(node->rightchild, x);
    return node;
}

void printBSTree(struct BSTreeNode * node) 
{   if(node != NULL)
    {   printBSTree(node->leftchild);
        tree += node->data+"_";
        printBSTree(node->rightchild);
    }
}

//--- insert button ---
void __fastcall TForm1::Button1Click(TObject *Sender)
{
    AnsiString data;
    data = Edit1->Text;
    root = insertBSTree(root, data);
    tree = "";
    printBSTree(root);
    Memo1->Lines->Add(tree);
}

Supposed that I insert A、B、C、D、E、F、G into the binary tree(Button1Click is the button to insert data into the binary tree) the binary tree should be like

      A
    /   \
   B     C
  / \   / \    
 H  J   D  E
       / \
      F   G

but it turned out to be like

 A   
  \    
   B
    \
     C
      \
       D
        \
         E
          \
           F
            \ 
             G

struct BSTreeNode ---> tree node

struct BSTreeNode * newNode(AnsiString x) ---> creating a new node

button1Click ---> insert the data from Edit->text; to the binary tree.

insertBSTree ---> if the node is null, then create a new node. Inserting the data into the leftchild/rightchild

Answer 1

You've created a binary search tree when you use < to determine which branch to insert into:

struct BSTreeNode * insertBSTree(struct BSTreeNode * node , AnsiString x)  
{   if(node == NULL) return newNode(x);
    if(x < node->data)
        node->leftchild = insertBSTree(node->leftchild, x);
    else
        node->rightchild = insertBSTree(node->rightchild, x);
    return node;
}

Your second example is a binary search tree, just not a balanced one.

Your expected result cannot be created by the functions shown because they maintain a strict invariant where the left branch must only contain values less than the root. The efficiency involved in a binary search tree only applies to balanced ones.

A balanced binary search tree containing this data would look like the following, because all trees involved (including subtrees) are balanced.

       D
      / \
     /   \
    /     \
   B       F    
  / \     / \
 A   C   E   G

You can get to this by adding a mechanism to check if your tree is balanced, and making adjustments by "rotating" trees left or right.

A
 \
  B
   \
    C

Becomes balanced, by rotating left around the smallest value on the right side of the tree.

   B
  / \
 A   C

To balance your initial tree:

 A   
  \    
   B
    \
     C
      \
       D
        \
         E
          \
           F
            \ 
             G

You'd check each subtree to see if it's balanced. The first subtree that is unbalanced is E, F, G.

 A   
  \    
   B
    \
     C
      \
       D
        \
         F
        / \
       E   G

We'd then see that D, E, F, G is unbalanced to the right.

 A   
  \    
   B
    \
     C
      \
       E
      / \
     D   F
          \
           G

And so on...

 A   
  \    
   B
    \
     D
    / \
   C   E
        \
         F
          \
           G

 A   
  \    
   B
    \
     D
    / \
   C   F
      / \
     E   G

 A   
  \    
   C
  / \
 B   D
      \
       F
      / \
     E   G

 A   
  \    
   C
  / \
 B   E
    / \
   D   F
        \
         G

  A   
   \    
    D
   / \
  C   E
 /     \
B       F
         \
          G

  A   
   \    
    D
   / \
  C   F
 /   / \
B   E   G

    B   
   / \    
  A   C
       \
        D
         \
          F
         / \
        E   G

    B   
   / \    
  A   C
       \
        E
       / \
      D   F
           \
            G

    B   
   / \    
  A   D
     / \
    C   E
         \
          F
           \
            G

    B   
   / \    
  A   D
     / \
    C   F
       / \
      E   G

    C   
   / \    
  B   D
 /     \
A       F
       / \
      E   G

    C   
   / \    
  B   E
 /   / \
A   D   F
         \
          G

If we go another few steps further:

      D   
     / \    
    C   E
   /     \
  B       F
 /         \
A           G

      D   
     / \    
    B   E
   / \   \
  A   C   F
           \
            G

       D
      / \
     /   \
    /     \
   B       F    
  / \     / \
 A   C   E   G