1

Thanks for your help

Background

I have a question about locating nodes in a tree.

I have a simple binary tree. Each node has a piece of data in it. Lets say it looks like this: 

  a
 / \
b   c

Where a=root, b=root.left, c=root.right

The tree is not created manually. Let's say I get a request to add new_data to node c.

I'm confused about how to know where c is without explicitly writing root.right.data=new_data.

My first thought is to create some type of helper dictionary with references to the node locations, like:

helper = {
    'a'= root,
    'b'= root.left,
    'c'= root.right
}

So that when I get a request, I can go to the helper and say something to the effect of:

helper.get('c').data=new_data

Questions

Am I in the right ballpark here? Recursively searching an entire tree repeatedly seems a bit much - this helper could be updated occasionally when the tree changes its node structure.

I'm confused about how to actually return my location for each node when I do recursively crawl the tree. How can I create this helper?

martineau
  • 119,623
  • 25
  • 170
  • 301
JW2
  • 349
  • 2
  • 16
  • 1
    You might have a look at this answer: https://stackoverflow.com/questions/2598437/how-to-implement-a-binary-tree – Ivonet Nov 11 '18 at 19:52
  • Why you need the tree anyway ? why not just put your data in a dictionary and that's all ? – Schidu Luca Nov 11 '18 at 19:55
  • @SchiduLuca I've simplified the example dramatically. The tree provides critical links between parent and child objects which can act on each other in different ways. The tree provides a very nice structure for this. I don't believe a dictionary would be productive. – JW2 Nov 11 '18 at 20:11
  • @JW2 ``Recursively searching an entire tree repeatedly seems a bit much`` . If you decided to put your data in such a form then it's ok to traverse recursively. If you think it's too much just don't use the tree at all.. – Schidu Luca Nov 11 '18 at 20:20

2 Answers2

0

If you have a reference to node c, you can use it directly, like so c.data=new_data.

Otherwise, if what you get is e.g. a string, then:

  1. Is your tree sorted, or can it be sorted? (i.e. is it a BST?) If so, use it.
  2. If it's not, then is there any other property of the tree/nodes that you can use to prune the search? (i.e. you have some information to limit where to search). If so, use it. If you don't know if you can use it, you should specify whatever properties your data has in your question.
  3. If the node can be anywhere, then you pretty much do have to search the whole tree (since the node you want can be anywhere). If that's the case though, is there a purpose to the tree structure? Maybe a hash table might be useful instead. (You could index the tree after you get it)

btw. Note that searching the tree should be O(n) in size of the tree, up to you if that's excessive or not.

Eric
  • 5,686
  • 2
  • 23
  • 36
  • it is a BST. Each node does have a unique identifier. I think you're right - whether I'm searching a helper dictionary for that key `helper.get(key)` or I'm traversing the tree I am still doing a search. It's not immediately evident to me how though to return the instance of a node when I search for it. – JW2 Nov 11 '18 at 20:14
  • Ah, in that case, you can refer to _find() method in this answer https://stackoverflow.com/a/28864021/272515 that Ivonet linked (note that it doesn't actually use self except to reference the _find method recursively. So it should be trivial to convert to a function for your purpose) – Eric Nov 11 '18 at 21:03
0

Answer

The answer is to recursively search. My thoughts of helper dict stem from my unfamiliarity w/ BST. I added the following to my nodes to search the tree preorder:

def find_node(self, start, id):
    if start:
        if start.id == id:
            return start
        else:
            node = self.find_node(start.left, id)
            if node:
                return node
            else:
                node = self.find_node(start.right, id)
                if node:
                    return node
    else:
        return None

This video was super helpful in helping me understand BST. I realized instead of just printing the traversal I could return the actual instance of the class itself when I found the right id.

JW2
  • 349
  • 2
  • 16