CODEWITHSUNDEEP
javasearchtreechildren
natan
natan

Reputation: 11

How to search a tree with three children nodes?

My tree nodes have the 3 string fields and 3 node fields which are left, middle and right.

One of the problems is that the method can only take string as a parameter

This is what I have 

public TreeNode findNode(String name) {
    TreeNode pointer = this.getRoot();

    if (pointer.getName().equals(name))
        return pointer;
    if (pointer.getLeft() != null)
        pointer = pointer.getLeft();
    findNode(name);
    if (pointer.getMiddle() != null)
        pointer = pointer.getMiddle();
    findNode(name);
    if (pointer.getRight() != null)
        pointer = pointer.getRight();
    findNode(name);
    return null;

}

This causes a stack overflow error because I just keep setting the pointer to root. But I have to start somewhere and my only parameters for the method can be name. I can't seem to see how to do this.

Upvotes: 1

Views: 945

Answers (4)

Vivin Paliath
Vivin Paliath

Reputation: 95568

Use an auxiliary method that takes in a TreeNode parameter in addition to the string:

public TreeNode findNode(String name) {
    return auxFindNode(this.getRoot(), name);
}

private TreeNode auxFindNode(TreeNode node, String name) {
    //perform your recursive traversal here
}

Your code as it stands will never work because you keep setting pointer to the root of the tree at the beginning of the method. So all your recursive calls start with the root of the tree.

If you prefer not to use another method, you can traverse the tree iteratively by using stack:

public TreeNode findNode(String name) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode foundNode = null;


    while(!stack.empty() && foundNode == null) {
        TreeNode node = stack.pop();

        if(node.getName().equals(name)) {
            foundNode = node;
        } else {
            if(node.getLeft() != null) {
                stack.push(node.getLeft();
            }

            if(node.getMiddle() != null) {
                stack.push(node.getMiddle());
            }

            if(node.getRight() != null) {
                stack.push(node.getRight());
            }
        }            
    }

    return foundNode;
}

Upvotes: 0

Abraham Sanchez
Abraham Sanchez

Reputation: 199

In all three cases (left, middle, right), you are calling findNode(name) but not for those objects, instead it is for this. That's why you get stack overflow.

Upvotes: 0

Jamie
Jamie

Reputation: 1937

You can use a list as a parameter stack.

public TreeNode findNode(String name) {
    List<TreeNode> stack = new ArrayList<TreeNode>();
    stack.add(this.getRoot());
    while (!stack.isEmpty())
    {
        TreeNode node = stack.remove(0);
        if (node.getName().equals(name))
            return node;
        if (pointer.getLeft() != null)
            stack.add(node.getLeft());
        if (node.getMiddle() != null)
            stack.add(node.getMiddle());
        if (node.getRight() != null)
            stack.add(node.getRight());
    }
    return null;
}

You can remove from the end of the list instead of the front of the list if you want to search depth-first.

Upvotes: 1

smk
smk

Reputation: 5882

Im guessing you cannot change the signature of this function. Have a helper function that takes in two parameters, (Node and name) that you call with root and name.

Upvotes: 0

Related Questions