Groovy web console

Subscribe to this site

Depth-first traversal of binary tree

Published 2 years ago by Valentin with tags tree dfs

class BinTree {
    BinTree left
    BinTree right
    String key

    void dfs(Closure f) {
        left?.dfs(f)
        f.call(this)
        right?.dfs(f)
    }

    void insert(String k) {
        if (k.compareTo(key) < 0) {
            if (left == null) {
                left = new BinTree(key: k)
            } else {
                left.insert(k)
            }
        } else {
            if (right == null) {
                right = new BinTree(key: k)
            } else {
                right.insert(k)
            }
        }
    }

    void printNode() {
        print key + " ";
    }
}

def a = ["d", "a", "dd", "e", "h", "gg", "f", "b", "n", "v"]
def bt = new BinTree(key:a[0])
for(i = 1; i <a.size(); i++) {
    bt.insert(a[i])
}
bt.dfs{node -> node.printNode()}