'Subtree points to wrong root (traversal)
I have made a program that inserts nodes to a binary tree and then using a search method to check if a node exists in the created binary tree or not. If it exists, I have to print the subtree of the node searched and its level. It is able to produce the correct subtrees for some nodes but it is not able to do so for other nodes. I also have difficulty in handling generics.
Here is my expected output:
ht=5 [K=G L=[K=D L=[K=B] R=[K=E]] R=[K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]]] // created binary tree
G [K=G L=[K=D L=[K=B] R=[K=E]] R=[K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]]], level=0
T [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=1
D [K=D L=[K=B] R=[K=E], level=1
Q [K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S], level=2
B [K=B], level=2
L [K=L L=[K=H] R=[K=N L=[K=M]]], level=3
E [K=E], level=2
N [K=N L=[K=M]], level=4
S [K=S], level=3
M [K=M], level=5
H [K=H], level=4
Then here is my output:
ht=5 [K=G L=[K=D L=[K=B] R=[K=E]] R=[K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]]] // created binary tree
G [K=G L=[K=D L=[K=B] R=[K=E]] R=[K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]]], level=0 // correct subtree
T [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=1 // correct subtree
D [K=D L=[K=B] R=[K=E], level=1 // correct subtree
Q [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=2
B [K=D L=[K=B] R=[K=E], level=2
L [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=3
E [K=D L=[K=B] R=[K=E], level=2
N [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=4
S [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=3
M [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=5
H [K=T L=[K=Q L=[K=L L=[K=H] R=[K=N L=[K=M]]] R=[K=S]], level=4
Problem: as you can see, it is not able to produce the correct starting K (root) for the nodes starting at
level=2
Here is my code for reference: Main Class
BST<Character> bst1 = new BST<>();
// insert values to bst1
String str = "GTDQBLENSMH";
char[] letter = str.toCharArray();
for (int i = 0; i < letter.length; i++) {
Character c = letter[i];
bst1.insert(c);
}
// print bst1
System.out.println("\nht=" + bst1.findHeight(bst1.root) + " " + bst1.toString() + "\n");
// search values in bst1
String str2 = "GTDQBLENSMH";
char[] letter2 = str2.toCharArray();
for (int i = 0; i < letter2.length; i++) {
Character c = letter2[i];
if (bst1.search(c) != null) { // if found
System.out.println(c + " ");
bst1.printExistingSubTree(bst1.root, c);
}
else { // if not found
System.out.println(c + " is not found.");
}
}
BST<T extends Comparable> extends BT Class
// insert(), findHeight(), search() methods
// prints the subtree with its level
public BTNode<T> printExistingSubTree(BTNode<T> node, T k) {
if (find(node.left, k, 1) != -1) {
printTree(node.left);
System.out.println("\b" + ", level=" + find(node.left, k, 1));
return node.left;
}
if (find(node.right, k, 1) != -1) {
printTree(node.right);
System.out.println("\b" + ", level=" + find(node.right, k, 1));
return node.right;
} else {
printTree(node);
System.out.println("\b" + ", level=0");
}
return null;
}
// find the level
public int find(BTNode<T> node, T k, int level) {
if(node.info.compareTo(k) == 0) {
return level;
}
int left = -1;
if(node.left != null) {
left = find(node.left, k, level + 1);
}
if(left != -1) {
return left;
}
int right = -1;
if(node.right != null) {
right = find(node.right, k, level + 1);
}
return right;
}
// creates the subtree
public void printTree(BTNode<T> node)
{
if (node == null) {
return;
}
if (node != null) {
System.out.println("\b[K=" + node.info);
if (node.left != null) {
System.out.println("\b L=");
printTree(node.left);
System.out.println("\b]");
}
if (node.right != null) {
System.out.println("\b R=");
printTree(node.right);
System.out.println("\b]");
}
}
}
BTNode Class
public class BTNode<T> {
T info;
int level;
BTNode<T> left, right;
public BTNode(T el) {
this(el, null, null);
}
public BTNode(T el, BTNode<T> l, BTNode<T> r) {
info = el;
left = l;
right = r;
}
}
BT Class
public class BT<T> {
BTNode<T> root = null;
int height = 0;
public BT() {
BTNode<T> node = new BTNode("");
}
public void setRoot(BTNode<T> n) {
this.root = n;
}
public String toString() {
return toString(root);
}
public String toString(BTNode<T> n) {
String s = "";
if (n == null) {
return "";
}
if (n != null) {
s = "[K=" + n.info;
if (n.left != null) {
s = s + " L=" + toString(n.left) + "]";
}
if (n.right != null) {
s = s + " R=" + toString(n.right) + "]";
}
}
return s;
}
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
