woven coral
I need to traverse a binary tree in a way that i only print out the nodes that are not the boundaries of the BST. I cant seem to think of a simple solution. The best i thought of is to just traverse the boundary add them all to an ArrayList and then just traverse the BST again and check if the ArrayList contains the element. I will watch a picture that will better explain the task. The green nodes are the ones that are the result. Looking for tips and suggestions not code.
tacit swanBOT
⌛ This post has been reserved for your question.
Hey @woven coral! Please use
/closeor theClose Postbutton above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.
TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.
woven coral
i want to add as well that there are no requirements in terms of asymptotic complexity
open iris
ok I would traverse it with two boolean variables
one storing whether I went left already and one storing whether I went right already
I would then only print nodes where I went both left and right and the node has children
like a node is on the boundary if any of the following is true
the question is what should happen with a case like this:
. B
/ \
B B
/ \
M B
/
?
i forgot to add that the BST is always a full one. meaning that each node either has 2 child nodes or 0.
open iris
like a node is on the boundary if any of the following is true
- node is a leaf
...
then this works without issues
woven coral
okay. so would you go to each node and check if its a leaf or it can be reached by going left or by going right from the root?
open iris
I would check whether reaching it requires going left AND right
if you have some zig-zag movement (and there are children), it isn't at the border
woven coral
i see. it's kind of complicated no? as you would need to evaluate the two branches from different sides. Because for the left branch it is going right for the right it is going left
open iris
You said that wouldn't matter but you can implement this without losing anything with respect to complexity
open iris
i see. it's kind of complicated no? as you would need to evaluate the two branch...
not really complicated
you just need to know
and print it if all of them are false
woven coral
idk if you are interested but here is my solution, it produces the results. might not be the most effective but still
if (root == null) {
return;
}
System.out.println("Inner nodes excluding root and perimeter nodes:");
findInnerNodes(root);
}
private void findInnerNodes(BstNode<E> node) {
if (node == null) {
return;
}
findInnerNodes(node.left);
if (node != root && !isLeaf(node) && !isOnPerimeter(node.element)) {
System.out.println("Inner node: " + node.element);
}
findInnerNodes(node.right);
}
private boolean isLeaf(BstNode<E> node) {
return node.left == null && node.right == null;
}
private boolean isOnPerimeter(E element){
if(isOnRightPerimeter(element, root) || isOnLeftPerimeter(element, root))
return true;
return false;
}
private boolean isOnRightPerimeter(E element, BstNode<E> node){
while(node != null){
if(element.compareTo(node.element) == 0)
return true;
node = node.right;
}
return false;
}
private boolean isOnLeftPerimeter(E element, BstNode<E> node){
while(node != null){
if(element.compareTo(node.element) == 0)
return true;
node = node.left;
}
return false;
}```As I said, if you store a little more data, you can do it more effectively
if you want to
you don't need to traverse the tree up