Databases
StackOverflow2013
Postsdbo
POCreating Java binary search tree
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POCreating Java binary search tree
    primarykey
    data
    text
    <p>So here is the Node class:</p> <pre><code>public class Node { private int _info; private Node _left; private Node _right; public Node() { //this._info = Integer.MIN_VALUE; this._left = null; this._right = null; } public int getInfo() { return _info; } public void setInfo(int _info) { this._info = _info; } public Node getLeft() { return _left; } public void setLeft(Node _left) { this._left = _left; } public Node getRight() { return _right; } public void setRight(Node _right) { this._right = _right; } } </code></pre> <p>How I create the tree:</p> <pre><code>public class BalancedBinaryTree { private ArrayList&lt;Integer&gt; _numbers; private Node _root; public BalancedBinaryTree(ArrayList&lt;Integer&gt; numbers) { this._numbers = new ArrayList&lt;&gt;(); this._numbers.addAll(numbers); Collections.sort(this._numbers); this._root = new Node(); this.create(this._root, 0, this._numbers.size()); } private void create(Node tree, int i, int j) { if (i &lt; j) { int m = i + (j - i) / 2; tree.setInfo(this._numbers.get(m)); tree.setLeft(new Node()); create(tree.getLeft(), i, m); tree.setRight(new Node()); create(tree.getRight(), m + 1, j); } } </code></pre> <p>This method computes the depth:</p> <pre><code> public static int getDepth(Node node) { if (node == null) { return 0; } else { int max = 0; if (getDepth(node.getLeft()) &gt; getDepth(node.getRight())) { max = getDepth(node.getLeft()); } else { max = getDepth(node.getRight()); } return max + 1; } } </code></pre> <p>And these two combined should print the tree by its levels:</p> <pre><code> public static void printLevel(Node node, int levelToDisplay, int currentLevel) { if (node != null) { printLevel(node.getLeft(), levelToDisplay, currentLevel); if (currentLevel == levelToDisplay) { System.out.print(node.getInfo() + " "); } currentLevel++; printLevel(node.getRight(), levelToDisplay, currentLevel); } } public static void printLevels(Node node) { for (int i = 0; i &lt; getDepth(node); i++) { System.out.println("Level :" + i); printLevel(node, i, 0); System.out.println(); } } </code></pre> <p>In a test class I have:</p> <pre><code> testNumbers.add(15); testNumbers.add(20); testNumbers.add(25); testNumbers.add(30); testNumbers.add(35); testNumbers.add(40); testNumbers.add(45); BalancedBinaryTree tree = new BalancedBinaryTree(testNumbers); BalancedBinaryTree.printLevels(tree.getRoot()); </code></pre> <p>And I get this output:</p> <pre><code>Level :0 0 15 20 30 Level :1 0 0 25 0 35 40 Level :2 0 0 0 45 Level :3 0 </code></pre> <p>I should get</p> <pre><code>Level :0 30 Level :1 20 40 Level :2 15 25 35 45 </code></pre> <ol> <li>What's wrong with the <code>getDepth</code> method because it seems that it returns 4 levels instead of 3?</li> <li>Why are there additional nodes? (those zeroes)</li> </ol> <p>I'm pretty sure I solved the problems but I will need an explanation for the following:</p> <p>This is the modified <code>printlevel</code> method:</p> <pre><code>public static void printLevel(Node node, int levelToDisplay, int currentLevel) { if (node.getLeft() != null &amp;&amp; node.getRight() != null) { printLevel(node.getLeft(), levelToDisplay, currentLevel+1); if (currentLevel == levelToDisplay) { System.out.print(node.getInfo() + " "); } printLevel(node.getRight(), levelToDisplay, currentLevel+1); } } </code></pre> <p>As you can see I test now if the current node has childs instead of checking if the current node exists and this is why those zeroes appeard because the traversal reached the leafs that had no info assigned on their right and left childs.</p> <p>The thing I want to understand is the difference between incrementing <code>currentLevel</code> and then passing it to the call of <code>printLevel</code> and simply passing <code>currentLevel+1</code> to the call. Shouldn't it be the same thing ?</p> <p>And the <code>getDepth</code> function:</p> <pre><code>public static int getDepth(Node node) { if (node.getLeft() == null &amp;&amp; node.getRight() == null) { return 0; } else { int max = 0; if (getDepth(node.getLeft()) &gt; getDepth(node.getRight())) { max = getDepth(node.getLeft()); } else { max = getDepth(node.getRight()); } return 1 + max; } } </code></pre> <p>Same thing here: traversal reached the leafs and got one more call for its childs thus returning one additional level so again, the solution is to test if the current node has childs instead of checking if the current node exits.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USoneNewbieCoder
    1. USoneNewbieCoder
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POCreating Java binary search tree
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWelcome to Stack Overflow! Asking strangers to spot errors in your code by inspection is not productive. You should identify (or at least isolate) the problem by using a debugger or print statements, and running on a simple dataset, and then come back with a more specific question (once you've narrowed it down to a 10-line [test-case](http://sscce.org)).
      singulars
      1. POCreating Java binary search tree
      1. USOliver Charlesworth
    2. COIs this homework ? If so, tag it as such.
      singulars
      1. POCreating Java binary search tree
      1. USdee-see
    3. CO@OliCharlesworth like I'm the only one who had posts like this. So, to be more specific, in the <code>create</code> I have 2 constructor calls for the <code>Node</code> but if I put a print in the constructor, the number of prints do not correspond so the constructor is called too many times at some point in that recursive function
      singulars
      1. POCreating Java binary search tree
      1. USoneNewbieCoder
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload