Right view of binary tree without using queue in Java

Question

HERE is the c++ implementation for right view of binary tree without using queue. When I try to convert it to Java, it is not working. Here is my Java code:

(I think most likely it is because I have not understood the algorithm properly and handling of maxLevel pointers/reference)

public static void rightView(TreeNode tNode){
    int maxLevel = 0;
    rViewUtil(tNode, 1,maxLevel);
}

public static void rViewUtil(TreeNode tNode, int level, int maxLevel){
    if(tNode==null)
        return;
    if(maxLevel < level){
        System.out.print(tNode.value + " ");
        maxLevel = level;
    }
    rViewUtil(tNode.right, level+1, maxLevel);
    rViewUtil(tNode.left, level+1, maxLevel);
}

score 2 · Answer 1 · edited May 23 '17 at 11:57

2

Java is pass by value.

i.e. maxLevel = level; doesn't affect other maxLevel values.

In you case, you should remove parameter maxLevel and use static variable instead:

private static int maxLevel;

public static void rightView(TreeNode tNode){
    maxLevel = 0;
    rViewUtil(tNode, 1);
}

public static void rViewUtil(TreeNode tNode, int level){
    ...
}

Note: It's not thread safe

Alternatively, you may use AtomicInteger:

public static void rightView(TreeNode tNode){
    rViewUtil(tNode, 1, new AtomicInteger());
}

public static void rViewUtil(TreeNode tNode, int level, AtomicInteger maxLevel){
    ...
    if(maxLevel.get() < level){
        ...
        maxLevel.set(level);
    }
}

It stores volatile int under the hood.

Note: As @Daniel mentioned, it's in concurrent package and intended for multithreading applications.

Another option is to create your "own" mutable integer or reuse an existing one.

edited May 23 '17 at 11:57

Community

1
1

answered Feb 04 '15 at 17:36

lifus

8,074
1
19
24

1

@lifus Thanks a lot for replying. I knew this is what the problem is but still I am not able to understand it well. I am still passing maxLevel everytime to the function call, so no matter pass by value or reference ... shouldn't the change reflect in other calls ?? I know it is something simple that I am missing here related to call backs. – Andy897 Feb 04 '15 at 17:56
2

Don't use AtomicInteger, it is meant for concurrent applications, not reference uses. There is unfortunately no built in mutable Integer object, but you can create your own easily enough. – Daniel Feb 04 '15 at 17:57
@DavidS Didn't get it. – Andy897 Feb 04 '15 at 17:57
1

@Daniel Thank you. I came across this http://www.java2s.com/Code/Java/Data-Type/Amutableintwrapper.htm ... can you please suggest how to write a easy and less comprehensive mutable integer wrapper ? – Andy897 Feb 04 '15 at 17:58
@Daniel I agree, it was just an example that it's possible to avoid shared mutable state. – lifus Feb 04 '15 at 18:03
Thanks, @lifus. I will never doubt myself again! – DavidS Feb 04 '15 at 22:16

Juan Lopes · Accepted Answer · 2015-02-04T19:04:39.370

2

In the spirit of @lifus' answer, but avoiding mutable state, you can use the function return to set maxLevel

public static void rightView(TreeNode tNode){
    int maxLevel = 0;
    rViewUtil(tNode, 1,maxLevel);
}

public static int rViewUtil(TreeNode tNode, int level, int maxLevel){
    if(tNode==null)
        return;
    if(maxLevel < level){
        System.out.print(tNode.value + " ");
        maxLevel = level;
    }
    maxLevel = rViewUtil(tNode.right, level+1, maxLevel);
    maxLevel = rViewUtil(tNode.left, level+1, maxLevel);
    return maxLevel
}

edited Feb 04 '15 at 19:04

answered Feb 04 '15 at 18:53

Juan Lopes

10,143
2
25
44

Thanks for replying. But I didn't get the problem yet. I am anyway passing updated MaxLevel everytime so what is the problem. I am partially getting it almost there .. stil do not understand how the current code is problem. Can you please please give a example and explain in two lines why my current code is not working (I understand it has do with pass by value thing .. but how ?) – Andy897 Feb 04 '15 at 18:59
The problem is you set the value of `maxLevel` inside the function. In C++, both the recursive calls you make and the caller will see the change you make in the memory region `int* maxLevel` points. In your Java translation, only the subsequent recursive calls see the change, not the caller. – Juan Lopes Feb 04 '15 at 19:02
Yes, that's indeed the best option. – lifus Feb 04 '15 at 21:10

Right view of binary tree without using queue in Java

2 Answers2

Linked