Thread: Binary Search Tree Insert

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    68

    Binary Search Tree Insert

    Ok so we are doing Binary Search Trees. I have to do an insert function to add new data into the tree. The code below calls a recursive function to do this. However we are required to do this non recursively.

    I have absolutely no idea where to start for this. a little guidance would be greatly appreciated. Thank you

    Code:
    void Insert(string data)
    {
    	if (root != NULL)
    	{
    		Insert(data, root);
    	}
    	else
    	{
    		root = new node;
    		root->data = data;
    		root->left = NULL;
    		root->right = NULL;
    	}
    }

  2. #2
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    477
    Quote Originally Posted by bleuz View Post
    Ok so we are doing Binary Search Trees. I have to do an insert function to add new data into the tree. The code below calls a recursive function to do this. However we are required to do this non recursively.

    I have absolutely no idea where to start for this. a little guidance would be greatly appreciated. Thank you

    Code:
    void Insert(string data)
    {
    	if (root != NULL)
    	{
    		Insert(data, root);
    	}
    	else
    	{
    		root = new node;
    		root->data = data;
    		root->left = NULL;
    		root->right = NULL;
    	}
    }
    You simply loop through the tree, going down left or right as the data you want to insert dictates, until you find a 0-node. Then you create it and insert the data.
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You do it in the same way you append a node to a linked-list, except that you take one of two possible paths from each node. Can you append to a linked-list?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Sep 2009
    Posts
    68
    Quote Originally Posted by iMalc View Post
    You do it in the same way you append a node to a linked-list, except that you take one of two possible paths from each node. Can you append to a linked-list?
    Yes I can. so all im doing is checking whether my data to be inserted is less than or greater than. as i progress down a side?

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Yeah that's pretty much it. Make sure that you attach the node to the correct child of it's parent of course.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    One thread at a time -> Binary Search Trees
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. Binary Search Tree
    By willmhmd in forum C Programming
    Replies: 2
    Last Post: 12-16-2005, 01:35 PM
  3. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM