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);
}

Juan Lopes · Accepted Answer · 2015-02-04 19:04:39Z

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 4, 2015 at 19:04

answered Feb 4, 2015 at 18:53

Juan Lopes

10.7k2 gold badges27 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Andy897 Over a year ago

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 ?)

Juan Lopes Over a year ago

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.

lifus Over a year ago

Yes, that's indeed the best option.

Community · Accepted Answer · 2017-05-23 11:57:00Z

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, 2017 at 11:57

CommunityBot

11 silver badge

answered Feb 4, 2015 at 17:36

lifus

8,6021 gold badge21 silver badges24 bronze badges

5 Comments

Andy897 Over a year ago

@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.

Daniel Over a year ago

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.

Andy897 Over a year ago

@DavidS Didn't get it.

Andy897 Over a year ago

@Daniel Thank you. I came across this java2s.com/Code/Java/Data-Type/Amutableintwrapper.htm ... can you please suggest how to write a easy and less comprehensive mutable integer wrapper ?

lifus Over a year ago

@Daniel I agree, it was just an example that it's possible to avoid shared mutable state.

Collectives™ on Stack Overflow

Right view of binary tree without using queue in Java

2 Answers 2

3 Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related