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?

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.

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.