CODEWITHSUNDEEP
javalanguage-agnosticbinary-treetree-traversalcluster-analysis
reve_etrange
reve_etrange

Reputation: 2571

Skip nodes during binary tree traversal

I need to traverse a binary tree, skipping the children of any node for which a condition is met.

This implements a tree-guided clustering approach; the leaves of a subtree are considered a cluster when they collectively meet the condition.

It seems like the place to start would be pre-order traversal, but I'm not sure how to modify the algorithm to skip all the children of the current node.

Update

In addition to the two (correct) answers below, one can use the following Java libraries:

Upvotes: 2

Views: 1388

Answers (2)

Vlad
Vlad

Reputation: 18633

If by skipping all the children you mean not just direct descendants but their entire subtrees, you can do the following:

public void traverse(Node n){
    if (n==null)
        return;
    doSomethingWith(n);
    if (!conditionIsMet(n)){
        traverse(n.left);
        traverse(n.right);
    }
}

Upvotes: 2

Ray Tayek
Ray Tayek

Reputation: 10003

the first part is easy: 

class Tree {
    Tree(int data) {
        this.data = data;
    }
    Tree left, right;
    Object object;
    int data;
}
public class Main {
    static void myPreorder(Tree tree) {
        if (tree == null) return;
        if (tree.data > 2) {
            System.out.println("skipping " + tree.data);
            return;
        }
        System.out.println("visiting " + tree.data);
        myPreorder(tree.left);
        myPreorder(tree.right);
    }
    public static void main(String[] args) {
        Tree root = new Tree(1);
        root.left = new Tree(2);
        root.right = new Tree(3);
        root.right.left = new Tree(4);
        root.right.right = new Tree(5);
        myPreorder(root);
    }
}

the second part: " ... the leaves of a subtree are considered a cluster when they collectively meet the condition. ..." is hard. you would need to examine all of the leaves of a node to see that they met the skip condition.

Upvotes: 1

Related Questions