This is not a homework problem. I am studying binary search trees and trying to understand how the code works. I have the code, it works, but I want to understand it completely.

I have made comments of what I think code does and in the lines that I don't understand or not sure I have placed question marks in the beginning and at the end of comments that I would like someone with knowledge to help me learn it.

I am trying to follow this code by inserting number 2 in sample binary search tree I created in attached excel document. I would like to understand step by step how pointers move and how ultimately new node is inserted. I would like someone to take a look at attached file and below code and better clarify comments and make modifications to excel pointers if I am not reading it correctly.

I know this seems a lot of work, but I really appreciate your help. Please help as much as you can.

class BinarySearchTree
{
    private:
        struct tree_node //Node that contains two pointers and data field
        {
           tree_node* left;  //pointer to the left subtree
           tree_node* right; //pointer to the right subtree
           int data; //data contained in this node 
        };
        tree_node* root; //???Is this creating pointer root to first node????
    public:
        BinarySearchTree()
        {
           root = NULL; //???start with empty binary search tree????
        }
        
		bool isEmpty() const 
		{ 
			return root==NULL; //if root=0 return TRUE, otherwise return false
		}
        void print_inorder(); 
        void inorder(tree_node*); //???recursive function, but I don't understand why we need tree_node*???
        void print_preorder();
        void preorder(tree_node*); //???recursive function, but I don't understand why we need tree_node*???
        void print_postorder();
        void postorder(tree_node*); //???recursive function, but I don't understand why we need tree_node*???
        void insert(int); //function to insert data in BST
   
};

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)//Function to insert numbers
{
    tree_node *t = new tree_node; //Create new node t same as our original node in class defined earlier
    tree_node *parent; //??? Don't understand if this is a pointer to above node or something else????
    t->data = d; //Insert number in our node
    t->left = NULL; //put NULL in left side of new node
    t->right = NULL; //put NULL in right side of new node
    parent = NULL; //????Why is this needed????
  // is this a new tree?
  if(isEmpty()) root = t; //Check if tree is empty
  //If isEmpty TRUE then new node t points to same thing as root
  else
  {
    //Note: ALL insertions are as leaf nodes
    tree_node* curr; //define new pointer curr
    curr = root; //points to same thing as root
    // Find the Node's parent
    while(curr) //while curr!=NULL 
    {
        parent = curr; //????parent and curr point to the same thing while curr!=NULL
        if(t->data > curr->data) curr = curr->right; /*????If input is > than whats in currently, move 
		pointer curr to right node. What is the purpose of this code????*/
        else curr = curr->left; /*????If input is < than whats in curr data, move 
		pointer curr to left node. What is the purpose of this code????*/
    }

    if(t->data < parent->data) /*???I can see that this insert the node in correct place
	but don't understand how this is connected to previous few lines of code */
       parent->left = t;
    else
       parent->right = t;
  }
}

Recommended Answers

All 5 Replies

Why don't you read Andrew Tanenbaum's data structure book. It is explained there properly.

> tree_node* root; //???Is this creating pointer root to first node????
Yes, it's the root of the whole tree.

>root = NULL; //???start with empty binary search tree????
Correct, though an empty tree doesn't have to be just a null pointer. Often[1], you'll see trees with a dummy root for special case removal. In these trees the root is a node with no data and one of the links is the actual root that the client code sees.

>void inorder(tree_node*); //???recursive function, but
>I don't understand why we need tree_node*???
Then you probably don't understand recursion as well as you should. The parameter represents the current node you're processing, and it's a parameter because that's the most convenient way of persisting nodes down the recursive chain:

inorder ( root );
  inorder ( root->left );
    inorder ( root->left->left );
      ...

If you weren't using an argument then you would have to store the current node and manage both moving it forward as well as backtracking manually in the function to properly simulate the same behavior.

>tree_node *parent; //??? Don't understand if this
>is a pointer to above node or something else????
In tree terminology, the parent is the first node above the current node you're looking at:

A
B       C
      D    E

A is the parent of C and B, C is the parent of D and E. Depending on the implementation, either a null pointer or a dummy node could be the parent of A.

>parent = NULL; //????Why is this needed????
Technically it isn't, but it clearly states the intention that the parent of the root node is a null pointer, so I would say it's a decent practice to explicitly initialize the pointer.

>parent = curr; //????parent and curr point
>to the same thing while curr!=NULL
No. parent is set to curr, then curr is updated to one of its children. When the loop ends, parent will be the parent of whatever node curr points to. Step through it with a paper and pencil, and no assumptions. You'll see how it works.

>/*????If input is > than whats in currently, move pointer
>curr to right node. What is the purpose of this code????*/
The point is to move curr down the tree until it reaches a leaf. Once again, your question betrays a failure to step through the code.

>/*???I can see that this insert the node in correct place but don't
>understand how this is connected to previous few lines of code */
I can't help you there (or rather, I'm not going to hold your hand and describe exactly how an algorithm works in your code). The code is simple and obvious if you take the time to understand it.

[1] Not so much these days. Most of the trees I see are canned solutions from books (by mindless code monkeys) or common libraries. It's depressing when I interview people for jobs and they haven't even heard of intermediate data structures, much less implemented them successfully.

Thanks everyone especially NARUE. I wish you were my professor.

Thanks everyone especially NARUE. I wish you were my professor.

Who wouldn't ? :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.