Traverse two binary search trees in order at the same time

This is a discussion on Traverse two binary search trees in order at the same time within the C Programming forums, part of the General Programming Boards category; So the algorithm to traverse a binary search tree structure in C: Code: typedef struct Node { int ind; int ...

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    9

    Lightbulb Traverse two binary search trees in order at the same time

    So the algorithm to traverse a binary search tree structure in C:

    Code:
    typedef struct Node {
        int ind;
        int val;
        struct Node *left;
        struct Node *right;
    } Node;
    .. is simple:

    1. Traverse down to the smallest value by calling the traversal recursively:

    Code:
    while (Node != NULL) {
    traverse(Node->left);
    }
    2. Once at the smallest node, "access" the node and perform whatever action:

    Code:
    printf("%d", Node->val);
    3. Then go back to the previous node and check the right hand node (which is bigger than the left)

    Code:
    traverse(Node->right);


    My question is... I have two binary search trees with the data structure defined above.

    Each node of the tree has an index and a value.

    I want to go through and add up the values for each index, without having to repeatedly search the tree.

    (ie. I don't want to loop for every index... I only want to traverse each tree once).

    Is there any way of doing this in C? I haven't seen this anywhere else on the web. An idea I had was this code, but I've got stuck.. this one's really confusing me!

    Code:
    INPUT: Pointers to binary trees A and B
    OUTPUT: Pointer to tree n, the sum of A and B
    
    Node *add(Node *a, Node *b, Node *n)
    {
        
        // loop through a,b and add
        while (a!=NULL)
        {
            
            n = add(a->left, b, n);
            
            while (b!=NULL)
            {
            
                n = add(a, b->left, n);
            
                if (a->ind == b->ind)
                {
                    n = tr_insertNode(n, a->ind, (a->val + b->val));
                }
                else if (a->ind > b->ind)
                {
                    b = b->previous;
                    n = add_row(a->right, b, n);
                }
                else
                {
                    a = a->previous;
                }
            }
        }
        
        
    }
    By the way, tr_insertNode creates a new Node on the heap with the index and value specified, and returns a pointer to it.


    Has anyone got any ideas?

    Cheers

    Will
    Last edited by willm07; 01-10-2008 at 09:40 AM.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    So the index can appear many times, with different values, is that correct?

    I guess one way would be to have an array for all the indices, traverse the tree, and do something like:
    Code:
        arr[node->index] += node->value;
    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Dec 2007
    Posts
    9
    Forgot to say.. index can only appear once for any value, and most indexes don't appear at all.

    So a typical tree might contain only 4,26,45 and 74, for example.

    Therefore an array representation would waste a huge amount of memory.

    I have thought about copying a node index / value representation into a linked list and then going through the list one by one and adding to the second binary tree, but this would involve a lot of lookups on the second tree, so no good :/

    The ideal scenario would be to just go through each tree in order and add as you go. There is a similar algorithm here that I found, but this one is for linked lists:

    http://eecs.harvard.edu/~ellard/Q-97...20.html#smmAlg
    Last edited by willm07; 01-10-2008 at 11:39 AM.

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Traversing a tree needs recursion (or a stack), so it is "wasting" memory anyway? (And if your trees typically have only about 4 nodes, using a tree over an array is a huge waste of space anyway?)

    However, if you just want to traverse it, you don't need to do it in order. Simply follow the left pointer and if at end continue from the next right pointer.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Do the two trees have the exact same shape? If so, wouldn't this do what you want?
    Code:
    Node *add(Node *a, Node *b)
    {
        Node *n = NULL;
        // loop through a,b and add
        if (a != NULL && b != NULL)
        {
            n = tr_insertNode(a->ind, (a->val + b->val));
    
            n->left = add(a->left, b->left);
            n->right = add(a-right, b->right);
        }
        return n;
    }
    Or will the trees have the same indexes but are linked differently?
    Or can the trees even have different indexes in them?
    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
    Registered User
    Join Date
    Dec 2007
    Posts
    9
    Quote Originally Posted by anon View Post
    Traversing a tree needs recursion (or a stack), so it is "wasting" memory anyway? (And if your trees typically have only about 4 nodes, using a tree over an array is a huge waste of space anyway?)

    However, if you just want to traverse it, you don't need to do it in order. Simply follow the left pointer and if at end continue from the next right pointer.
    Yes but recursion is using a stack which will never be filled with all the data from the tree at the same time (as when a function finishes recursion, its value is removed) and therefore will never take up the same amount of memory as an array representation.

    Quote Originally Posted by iMalc
    Do the two trees have the exact same shape? If so, wouldn't this do what you want?
    Code:
    Node *add(Node *a, Node *b)
    {
    Node *n = NULL;
    // loop through a,b and add
    if (a != NULL && b != NULL)
    {
    n = tr_insertNode(a->ind, (a->val + b->val));

    n->left = add(a->left, b->left);
    n->right = add(a-right, b->right);
    }
    return n;
    }
    Or will the trees have the same indexes but are linked differently?
    Or can the trees even have different indexes in them?
    That is the problem.. the trees will not have the same indexes in them, and the structures will be different. Therefore the above algorithm is no good!

    I'm beginning to think that it might be an idea to copy each tree into a linked list and then add the resulting lists, but that is quite wasteful.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    How large is this tree [or the range of your indices]?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,607
    You could just do an in-order traversal of both trees....
    Code:
    Add(Node A, Node B)
    {
        Node S;
        
        A = first_inorder(A);
        B = first_inorder(B);
    
        while (A && B)
        {
            if (A.idx == B.idx)
            {
                insert_node(S, A.idx, A.val + B.val);
            }
            else if (A.idx < B.idx)
            {
                insert_node(S, A.idx, A.val);
                A = next_inorder(A);
            }
            else
            {
                insert_node(S, B.idx, B.val);
                B = next_inorder(B);
            }
        }
    
        if (A)
            insert_remaining(S, A);
        if (B)
            insert_remaining(S, B);
    
        return S;
    }
    The only problem with this is that elements are added to 'S' in an in-order fashion. So unless your tree is self-balancing, you'll end up with a "worst case" tee (a linked list).

    gg

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I don't think that a linked-list solution has to be that wasteful. Roughly how many indices will there be? If the answer is "not a whole lot", then maybe some variation on the following idea will work:

    For each tree:
    1. Traverse the tree.
    2. For each node that we visit, look through our linked list for the index of the node.
    3a. If we find it, add the value of the current node to the value field of the list.
    3b. If we don't, add a new node to the linked list (perhaps even inserting in sorted order of index) with current index and value.

    (This assumes the problem is "for each index that appears, add up all the values of nodes with that index, in both trees together", as that's how I'm reading the problem statement.) The answer would have to use that much data anyway (<index, sum> pairs), so I don't see that we've used anything extra.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Quote Originally Posted by willm07 View Post
    That is the problem.. the trees will not have the same indexes in them, and the structures will be different. Therefore the above algorithm is no good!
    If they have none of the same indexes in them then how would you know when to add nodes together? I presume you mean that they may share some, but may also have others that are unique in each tree?
    Now you perhaps still need to define the output more precisely. Of the nodes that are unique to one of the trees, should these nodes appear in the output?
    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"

  11. #11
    Registered User
    Join Date
    Dec 2007
    Posts
    9
    Quote Originally Posted by iMalc View Post
    If they have none of the same indexes in them then how would you know when to add nodes together? I presume you mean that they may share some, but may also have others that are unique in each tree?
    Now you perhaps still need to define the output more precisely. Of the nodes that are unique to one of the trees, should these nodes appear in the output?
    Sorry, let me clarify.

    Each tree may or may not have unique indices.

    If an index is unique, then it should appear in the sum.

    So basically the sum is an ordered list of unique indices and the sums of non unique ones.

    Codeplug, thanks for the code you posted, I have tried it but still no luck. The problem is that you have to recurse backwards on right and left nodes of the tree.

    Quote Originally Posted by tabstop
    I don't think that a linked-list solution has to be that wasteful. Roughly how many indices will there be? If the answer is "not a whole lot", then maybe some variation on the following idea will work:

    For each tree:
    1. Traverse the tree.
    2. For each node that we visit, look through our linked list for the index of the node.
    3a. If we find it, add the value of the current node to the value field of the list.
    3b. If we don't, add a new node to the linked list (perhaps even inserting in sorted order of index) with current index and value.
    After thinking about this problem for a while and analysing a graph of the different runtimes, I agree with you and so I am going to go with the linked list implementation.

    2. For each node that we visit, look through our linked list for the index of the node.
    The algorithm I found here:
    http://eecs.harvard.edu/~ellard/Q-97...20.html#smmAlg

    .. avoids this step by recursing through the lists at the same time.

    So the worst case time complexity of each stage will be: (I think..)

    1. |a| - convert each tree to a linked list
    2. |a| - step through each list, comparing, adding individual elements, and inserting into a new binary tree

    Although:

    Quote Originally Posted by Codeplug
    The only problem with this is that elements are added to 'S' in an in-order fashion. So unless your tree is self-balancing, you'll end up with a "worst case" tee (a linked list).
    So I might try and add in a function to rebalance the tree afterwards (can't really think of a better solution).

    How does that look?
    Last edited by willm07; 01-11-2008 at 12:27 PM.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Okay, I just tried writing this myself and I've determined that it is probably not feasible without modifying the exisiting trees.
    I drew two trees with numbers between 1 and 10.
    Tree a had 4 as the root and 6 was a leaf node.
    Tree b had 6 as the root and 4 was a leaf node.
    When you start off you compare the two roots and must search for 6 in tree a, and search for 4 in tree b. That's two log(n) searches. Then you still have to decide which of those becomes the new root, and how the remaining children are linked on.
    Code:
         4           6
        / \         / \
       /   \       /   \
      2     8     2     8
     / \   / \   / \   / \
    1   3 6   9 1   4 7   9
    I think it would be doable if you can modify either of the existing tree structures in the process. Then you could treat one of them as a splay tree and say splay a for nodes that you come across in b. For example this would initially bring 6 to the top of tree a, making it a lot easier.

    I think it is still better to convert them both to lists.
    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"

  13. #13
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,607
    >> I have tried it but still no luck. The problem is that you have to recurse backwards on right and left nodes of the tree.
    Who says you *have* to recurse? If you want to avoid copying a entire tree to a list, all you need is a non-recursive in-order traversal - and some balancing code.

    gg

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    If you really want to you can convert the tree in-place into a list where the left and right pointers are actually prev and next pointers, using the following nifty little code snippet:
    Code:
    template Node *Tree2ListHelper(Node *list, Node *tree) {
    	for (;;) {
    		if (tree->right) {
    			list = Tree2ListHelper(list, tree->right);
    			list->left = tree;
    		} else if (list)
    			list->left = tree;
    		tree->right = list;
    		if (!tree->left)
    			return tree;
    		list = tree;
    		tree = tree->left;
    	}
    }
    
    Node *Tree2List(Node *tree) {
    	if (!tree)
    		return NULL;
    	return Tree2ListHelper(NULL, tree);
    }
    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"

  15. #15
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I like Codeplug's idea. Can't it be made to work something
    like this? (I haven't tested it yet.)
    Code:
    Node stack[ MAXTREEDEPTH ]; /* If you can live with a limit */
    int  stackTop = 0;
    
    Node first_inorder( Node N ) {
        while (N->left) {
            stack[ stackTop++ ] = N;
            N = N->left;
        }
        return N;
    }
    
    Node next_inorder( Node N ) {
        if (N->right) return first_inorder( N->right );
        return stack[ --stackTop ];
    }
    If that works then you can get a perfectly balanced tree by Add'ing
    into an array of pointers to the new sum nodes. Then construct a
    tree by a recursive binary search of the array, but always searching
    both ways (instead of always ignoring half), setting the left and right
    pointers of each element encountered to the next two elements to
    search (or zero), and then recursing on those.

    I also like the "nifty little code snippet" posted by iMalc!
    If this doesn't work, that will probably do it (and may be best anyway).
    Last edited by oogabooga; 01-12-2008 at 02:57 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with binary search.
    By StateofMind in forum C Programming
    Replies: 6
    Last Post: 05-06-2009, 02:14 PM
  2. Binary Search Trees
    By chaos in forum C Programming
    Replies: 1
    Last Post: 06-14-2005, 05:42 AM
  3. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 09:18 AM
  4. binary search tree
    By unregistered in forum C++ Programming
    Replies: 4
    Last Post: 12-11-2001, 10:42 AM
  5. Newbie questions regarding binary search trees
    By Ham in forum C++ Programming
    Replies: 1
    Last Post: 11-04-2001, 06:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21