How to remember the path while traverse a binary tree?
Hi, again, I have difficulty handling tree search problems.
The quesion is How to search for a node from a binary tree A, return true if found meanwhile generate the path which can be used to locate the node.
I think the signature should be:
// The path contains only 0s and 1s. 0 means go left and 1 means go right.
public staic boolean search(Node rootOfA, Node b, ArrayList<Integer> path){
}
// the class Node only has two fields:
Node{
Node left;
Node right;
}
I know if there is another field in the Node class (say, a flag), the quesion would be much easier, but the space is really critical.
I tried to use recursion but havn't got a correct solution. I am thinking of usinga non-recursion algo.
Anyone wants to help?
[818 byte] By [
since81a] at [2007-10-3 0:37:02]
> I know if there is another field in the Node class
> (say, a flag), the quesion would be much easier, but
> the space is really critical.
It doesn't make a real difference.
And what do you mean by really critical?
> I tried to use recursion but havn't got a correct
> solution. I am thinking of usinga non-recursion
> algo.
>
> Anyone wants to help?
You must have some sort of add-method already (probably recursive) to add nodes to your tree. Getting a path from the root to a specific node is almost the same as that add method.
In order to help you, you need to post what you've already got and tell where you're stuck.
> // the class Node only has two fields:> Node{> Node left;> Node right;> }What's the point of a structure if it can't hold anything? Doesn't it need to hold a value?
> // the class Node only has two fields:
> Node{
> Node left;
> Node right;
> }
What's the point of a structure if it can't hold anything? Doesn't it need to hold a value?
No, it does not need to hold any value. I use the shape of the tree to represent a value. Actually, I designed a codec which encodes integers into binary trees(using Catalan Number Theory) and decodes the integer value back.
So, the node class does not need to hold any value.
I think the quesion is relatively clear:
Given a binary tree, a node, test if the binary tree contains the node, generate a path that can be used to locate the node.
So, if the path is built correctly, I can simply follow a sequence of 0 and 1s, going left or right from the root of tree A to get to the node.
I am not so sure about your quesion " what you got". I can tell you "where i am stuck" is complete the search(Node, Node, path) function.
I didn't say any background information because I think it is irrelavant and I might not be able to explainit ver well.
Anyway, I hope I provided enough infomation this time:-)
Thanks for your interest!
public static boolean search(Node rootOfA, Node b, ArrayList<Integer> path) {
return search(rootOfA, b, path, 0);
}
private static boolean search(Node root, Node n, List list, int index) {
if (n == root) return true;
if (index >= list.size()) {
return false;
}
int leftOrRight = list.get(index)
if (leftOrRight = 0)
return search(root.left, n, list, index+1)
else
return search(root.right, n, list, index+1)
}
Well, rikippen, What your code solves is the "locate" problem when the path is given.What I want is how to generate a path that can be used in your code.Cheers.
> No, it does not need to hold any value. I use the
> shape of the tree to represent a value.
Ok, clear.
> I think the quesion is relatively clear:
>
> Given a binary tree, a node, test if the binary tree
> contains the node, generate a path that can be used
> to locate the node.
1 - How are you cmoparing nodes? By their references?
2 - How do you add a node? What are the rules to deceide whether they go to the left or to the right?
1. Yes. By reference. if nodeA == nodeB works just fine.
2. No need to add a node. At least in my problem, I do not need to consider adding nodes.
O- rootOfA
||
OO
||
OO -- nodeB
So, in the graph above, by calling search(rootOfA, nodeB,path) we should get "true", and the path will contain [0,1] which means if we go to the left (0) from rootOfA(so we come to rootOfA's left child) and then go right(1) from where we are (the left child of rootOfA) we will find nodeB.
That's the rule.
Hope it's clear enough now. :-)
> Hope it's clear enough now. :-)?Not at all. But maybe it's clear to someone else.Best of luck too you.
public Stack search(Node root, Node node, Stack path) {
if (root == null) return null;
if (root.equalss(node)) return path;
if (root.greaterThan(node)) {
path.push(0);
return search(root.left, node, path);
}
else {
path.push(1);
return search(root.right, node, path);
}
}
This is assuming that the Stack is empty when you start the search.
The method will return null when the node wasn't found, an empty
stack if the node equals the root of the tree, otherwise the 0,1
path leading to the node to be found.
kind regards,
Jos
JosAHa at 2007-7-14 17:30:52 >
Oh dear, I was assuming a binary search tree. Here's a method that walks
through an unordered binary tree:
Stack search(Node root, Node node, Stack path) {
if (root == null) return null;
if (root.equals(node)) return path;
path.push(0);
if (search(root.left, node, path) != null) return path;
path.pop();
path.push(1);
return search(root.right, node, path);
}
kind regards,
Jos
JosAHa at 2007-7-14 17:30:52 >
Hi, JosAh,
That's mind provoking. However, I do think it works. It does not pop some stuff it should pop. I tested it over a very simple tree and it failed. Did you test it? I might be wrong...
The tree I am working on does not have null pointers, the condition to test if a node is a leaf is if(node.right == right). Namly, all the right pointer of leaves points to itself.
So I changed your code to be:
Stack search(Node root, Node node, Stack<Integer> path) {
if (root == null || root.right ==right) return null;
if (root.equals(node)) return path;
path.push(0);
if (search(root.left, node, path) != null) return path;
path.pop();
path.push(1);
return search(root.right, node, path);
}I simply tested it with
Stack<Integer> path = new Stack<Integer>();
System.out.println( root, root.right.right, path);
root is the root of a complete binary tree with 7 nodes(4 leaves).
Apparenly, if the path is built correctly search(root, root.right.right, path) would return [1,1] whereas this seach returns [ 0 , 1, 1].
Considerring , the right branch never pops, I changed it into
Then I changed it to :
Stack search(Node root, Node node, Stack<Integer> path) {
if (root == null || root.right ==right ) return null;
if (root.equals(node)) return path;
path.push(0);
if (search(root.left, node, path) != null) return path;
path.pop();
path.push(1);
if (search(root.right, node, path) != null) return path;
path.pop();
return path;
}
With the same test case, it returns [].
I will keep working on it.
Cheers,
Message was edited by:
since81
Message was edited by:
since81
Problem solved!
Indeed, your code misses one pop every time it recursivly calls the search() if the search returns null.
Here is my solution:
// origin is a node whose right child is the root. It is the "root" in the notation of PPCT tree.
public static boolean search(Node origin, Node node, Stack<Integer> path){
if(origin == null)return false;
Node root = origin.right;
return search(root, node, path, 1);
}
private static boolean search(Node root, Node node, Stack<Integer> path, int direction){
path.push(direction);
if(root == node)return true;
if(root.right != root) // if root is not a leaf.{
if(!search(root.left,node,path,0)) {
path.pop();
if(!search(root.right, node,path,1)){
path.pop();
return false;
}
else{
return true;
}
}
else {
return true;
}
}
return false;
}
Thank you guys very much! Especially to JosAH!
> Indeed, your code misses one pop every time it recursivly calls the
> search() if the search returns null.
Yep, that was me, trying to be too clever again ;-) Change this last line:return search(root.right, node, path);
To this:if (search(root.right, node, path) != null) return path;
path.pop();
return null;
... that way it is symmetrical to the left subtree handling: it pops the
current try which wasn't successful.
> Thank you guys very much! Especially to JosAH!
You're welcome of course.
kind regards,
Jos
JosAHa at 2007-7-14 17:30:52 >
Even make your code that way, I doubt there would be some pop operation missing... like Search unsuccessful more than once while only pop once...You can test it with a simple test case (like the one I used). Thanks a a heap!
Man, I must've had my brains all backwards yesterday,edit: and today too ... forget my babbling please.I apologize.kind regards,Jos
