Get all nodes of a specific level of a Binary Tree

user_15070528 0
Viewed 1391

I have a BinaryTree and I want to get all nodes of a specific level. Order does not matter. I want to try to do this with recursion . My method looks like this:

public List<T> getNodesOnLevel(int i){
    int recursionTool = i
    //to do
    recursionTool-=1
    }

I tried to while(recursionTool != 0){ method.... and then recursionTool -1} But I ended up getting all nodes until the wanted level. My Node looks like this:

class Node<T>{
    T val;
    Node<T> left;
    Node<T> right;
    Node(T v){
        val = v;
        left = null;
        right = null;
    }
binary-tree recursion java
2 Answers

It is possible to implement this as a pure functional algorithm by concatenating the lists returned by recursive calls. Unfortunately, that is rather inefficient in Java because all retrieved values are copied by list creation or concatenation once at each recursion level.

If you are willing to use mutation, here is a solution that avoids the copying (assuming that this is a Node<T>):

private void getNodesOnLevel(int level, List<T> list) {
    if (node == null) return;
    if (level == 0) {
        list.add(this.val);
    } else {
        this.left.getNodesOnLevel(level - 1, list);
        this.right.getNodesOnLevel(level - 1, list);
    }
}

The above method needs to be called with an empty (mutable) list as the 2nd argument, so we need another method:

public List<T> getNodesOnLevel(int level) {
    List<T> list = new ArrayList<>();
    this.getNodesOnLevel(level, list);
    return list;
}

(In complexity terms, the pure functional solution is O(LN) where L is the level and N is the number of nodes at that level. My solution is O(N). Each value in the list will be copied twice on average, due to the way that ArrayList.append implements list resizing. The resizing could be avoided by creating the list with a capacity of 2level.)

user_1399850

This may help you. I had been used this method for print nodes but you can change it.

public void printGivenLevel(TNode root, int level) {
    if (root == null)
        return;
    if (level == 1 && root.getValue() != null) {
   //  here,  add  root.getValue() to list
    } else if (level > 1) {
        printGivenLevel(root.getLeft(), level - 1);
        printGivenLevel(root.getRight(), level - 1);
    }
}
user_131816070
Related