I am trying to write this code to print the given user inputs in a tree structure that follows
x
x x
x x
but it does not output that way. I am getting the output as
x
x
x
This is the function I have written that gets and prints:
private void inOrder(Node n)
{
if(n == null) // recursion ends when node is null
return;
{
inOrder(n.left);
System.out.println(n.data);
inOrder(n.right);
}
}
public void printInorder()
{
inOrder(root);
}
This approach runs into trouble because any calls to println() preclude printing further nodes on a line. Using a level order traversal/BFS will enable you to call println() to move to the next line only when all nodes on a given tree level have already been printed.
The bigger difficulty lies in keeping track of the horizontal placement of each node in a level. Doing this properly involves considering the depth, length of the node data and any empty children. If you can, consider printing your tree with depth increasing from left to right, similar to the unix command tree, rather than top-down, which simplifies the algorithm.
Here's a proof-of-concept for a top-down print. Spacing formulas are from this excellent post on this very topic. The strategy I used is to run a BFS using a queue, storing nodes (and null placeholders) in a list per level. Once the end of a level is reached, spacing is determined based on the number of nodes on a level, which is 2n-1, and printed. A simplifying assumption is that node data width is 1.
import java.util.*;
import static java.lang.System.out;
public class Main {
static void printLevelOrder(Node root) {
LinkedList<QItem> queue = new LinkedList<>();
ArrayList<Node> level = new ArrayList<>();
int depth = height(root);
queue.add(new QItem(root, depth));
for (;;) {
QItem curr = queue.poll();
if (curr.depth < depth) {
depth = curr.depth;
for (int i = (int)Math.pow(2, depth) - 1; i > 0; i--) {
out.print(" ");
}
for (Node n : level) {
out.print(n == null ? " " : n.val);
for (int i = (int)Math.pow(2, depth + 1); i > 1; i--) {
out.print(" ");
}
}
out.println();
level.clear();
if (curr.depth <= 0) {
break;
}
}
level.add(curr.node);
if (curr.node == null) {
queue.add(new QItem(null, depth - 1));
queue.add(new QItem(null, depth - 1));
}
else {
queue.add(new QItem(curr.node.left, depth - 1));
queue.add(new QItem(curr.node.right, depth - 1));
}
}
}
static int height(Node root) {
return root == null ? 0 : 1 + Math.max(
height(root.left), height(root.right)
);
}
public static void main(String[] args) {
printLevelOrder(
new Node<Integer>(
1,
new Node<Integer>(
2,
new Node<Integer>(
4,
new Node<Integer>(7, null, null),
new Node<Integer>(8, null, null)
),
null
),
new Node<Integer>(
3,
new Node<Integer>(
5,
new Node<Integer>(9, null, null),
null
),
new Node<Integer>(
6,
null,
new Node<Character>('a', null, null)
)
)
)
);
}
}
class Node<T> {
Node left;
Node right;
T val;
public Node(T val, Node left, Node right) {
this.left = left;
this.right = right;
this.val = val;
}
}
class QItem {
Node node;
int depth;
public QItem(Node node, int depth) {
this.node = node;
this.depth = depth;
}
}
Output:
1
2 3
4 5 6
7 8 9 a
You have a problem to print the way you want. An In order will print left, current and right. These are in different levels in the tree. As soon you print a down level you can't print the current one above because it was already printed.
Also don't forget the println will print that string and give a new line after.
To have a fancy design, you probably need to do some fancy engineering to align them perfectly, something like this:
You need a Queue for the nodes to visit.
printNode(Node root, queueWithNodesAndStartAndEnd, start, end)
print me at the middle of start and end
put my left child in the queue with start = myStart and end = middle of my start and my end
put my right child in the queue with start = middle of my start and my end and end = my end
pop (get and remove) first element from queue
if not empty print popped node with start and end provided
I know this is pseudo-code but you should be able to implement it.
This is the nicest solution I've seen: https://stackoverflow.com/a/42449385/9319615
Here is my code snippet leveraging it. This class will run as is.
class Node {
final int value;
Node left;
Node right;
Node(int value) {
this.value = value;
right = null;
left = null;
}
public void print() {
print("", this, false);
}
private void print(String prefix, Node n, boolean isLeft) {
if (n != null) {
System.out.println(prefix + (isLeft ? "|-- " : "\\-- ") + n.value);
print(prefix + (isLeft ? "| " : " "), n.left, true);
print(prefix + (isLeft ? "| " : " "), n.right, false);
}
}
}
class BinaryTree {
Node root;
private Node addRecursive(Node current, int value) {
if (current == null) {
return new Node(value);
}
if (value < current.value) {
current.left = addRecursive(current.left, value);
} else if (value > current.value) {
current.right = addRecursive(current.right, value);
} else {
// value already exists
return current;
}
return current;
}
public void add(int value) {
root = addRecursive(root, value);
}
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
System.out.print(" " + node.value);
traverseInOrder(node.right);
}
}
}
public class Main {
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
bt.add(6);
bt.add(4);
bt.add(8);
bt.add(3);
bt.add(5);
bt.add(7);
bt.add(9);
System.out.println("Print in order->");
bt.traverseInOrder(bt.root);
System.out.println("\n\nPrint Tree Structure");
bt.root.print();
}
}
