Create a full and complete binary tree recursively
0
Purpose:
I would like to create a full and complete binary tree, which saves a String value in its leaves, recursively.
Example 1:
Let's say you want to save two Strings in your tree. So you will need a root and two leaves.
* <- root node
/
v0 v1 <- leaves
Example 2:
Let's say you want to save three Strings in your tree. So you will need a root, two inner Nodes but four leaves, so the tree is still complete.
* <- root node
/
+ + <- inner node
/
/
/ /
v0 v1 v2 v3 <- leaves
Math trickery:
Its fairly straightforward to calculate the specs for the binary tree.
Height: ⌈log2 expectedNumOfStrings⌉
double height = Math.log(expectedNumOfStrings) / Math.log(2);
int roundedHeight = (int) Math.ceil(height);
Number of leaves: 2Height
int numOfLeaves = (int) Math.pow(2, roundedHeight);
Number of inner Nodes: 2h − 1
int numOfInnerNodes = (int) (Math.pow(2, roundedHeight)-1)
Implementation:
Let's implement a couple of classes for this binary tree. We'll need a BinaryTree class.
/**
* Create a complete binary tree recursively depending on the expected leaves.
*/
public class BinaryTree {
private InnerNode root;
private LeafNode current;
public BinaryTree(int expectedNumOfStrings) {
//sets root node
this.root = new InnerNode();
//set inner nodes
root.createInnerNodes(expectedNumOfStrings);
//set leaves
root.createLeaves(expectedNumOfStrings);
//The way things are now the tree isn't created in one go.
//I'll have to traverse it again for the leaves.
}
}
All elements of the tree share a link to the parent (for the root it's null). Let's create a class TreeNode:
public class TreeNode {
private TreeNode parent;
}
Now let's create InnerNode and LeafNode which just extends TreeNode.
public class InnerNode extends TreeNode {
private BinaryTree left;
private BinaryTree right;
//used to set the root node
public InnerNode() {
super.parent = null;
this.left=null;
this.right=null;
}
public InnerNode(InnerNode parent) {
super.parent= parent;
}
public TreeNode createInnerNodes(int expectedValues) {
//recursive magic happens here. But how?
}
}
and
public class LeafNode extends TreeNode {
private String data;
public LeafNode(InnerNode parent) {
super.parent= parent;
}
public LeafNode createLeaves(int numOfLeaves) {
//recursive magic happens here again. But how?
}
}
Questions and Problems
- I want to keep the classes as separated as they are and I want to set the Tree up in one go. How to I set up
InnerNodesandLeavesat the "same" time?
InnerNode leftandInnerNode rightare private so I can only access them from withinInnerNode. But how do I deal with the leaves then? Can I just pass the root Node though toInnerNode/Leavesin a method?- What is best used for the recursion? Height or Number of corresponding nodes? Or something else entirely?
- How do you set the left and right pointer? I mean the objects to which they point don't exist yet, do they?
- Am I on the right track? /o
java recursion binary-tree
asked Nov 23 '18 at 16:56
kiaora
226
add a comment |
0
Purpose:
I would like to create a full and complete binary tree, which saves a String value in its leaves, recursively.
Example 1:
Let's say you want to save two Strings in your tree. So you will need a root and two leaves.
* <- root node
/
v0 v1 <- leaves
Example 2:
Let's say you want to save three Strings in your tree. So you will need a root, two inner Nodes but four leaves, so the tree is still complete.
* <- root node
/
+ + <- inner node
/
/
/ /
v0 v1 v2 v3 <- leaves
Math trickery:
Its fairly straightforward to calculate the specs for the binary tree.
Height: ⌈log2 expectedNumOfStrings⌉
double height = Math.log(expectedNumOfStrings) / Math.log(2);
int roundedHeight = (int) Math.ceil(height);
Number of leaves: 2Height
int numOfLeaves = (int) Math.pow(2, roundedHeight);
Number of inner Nodes: 2h − 1
int numOfInnerNodes = (int) (Math.pow(2, roundedHeight)-1)
Implementation:
Let's implement a couple of classes for this binary tree. We'll need a BinaryTree class.
/**
* Create a complete binary tree recursively depending on the expected leaves.
*/
public class BinaryTree {
private InnerNode root;
private LeafNode current;
public BinaryTree(int expectedNumOfStrings) {
//sets root node
this.root = new InnerNode();
//set inner nodes
root.createInnerNodes(expectedNumOfStrings);
//set leaves
root.createLeaves(expectedNumOfStrings);
//The way things are now the tree isn't created in one go.
//I'll have to traverse it again for the leaves.
}
}
All elements of the tree share a link to the parent (for the root it's null). Let's create a class TreeNode:
public class TreeNode {
private TreeNode parent;
}
Now let's create InnerNode and LeafNode which just extends TreeNode.
public class InnerNode extends TreeNode {
private BinaryTree left;
private BinaryTree right;
//used to set the root node
public InnerNode() {
super.parent = null;
this.left=null;
this.right=null;
}
public InnerNode(InnerNode parent) {
super.parent= parent;
}
public TreeNode createInnerNodes(int expectedValues) {
//recursive magic happens here. But how?
}
}
and
public class LeafNode extends TreeNode {
private String data;
public LeafNode(InnerNode parent) {
super.parent= parent;
}
public LeafNode createLeaves(int numOfLeaves) {
//recursive magic happens here again. But how?
}
}
Questions and Problems
- I want to keep the classes as separated as they are and I want to set the Tree up in one go. How to I set up
InnerNodesandLeavesat the "same" time?
InnerNode leftandInnerNode rightare private so I can only access them from withinInnerNode. But how do I deal with the leaves then? Can I just pass the root Node though toInnerNode/Leavesin a method?- What is best used for the recursion? Height or Number of corresponding nodes? Or something else entirely?
- How do you set the left and right pointer? I mean the objects to which they point don't exist yet, do they?
- Am I on the right track? /o
java recursion binary-tree
asked Nov 23 '18 at 16:56
kiaora
226
I feel like having separate classes for root, inner and leaf nodes is a bit over-engineered. Since trees are recursive, it makes good sense to only have one node class. May I also ask why you're only storing data in leaves? Why do you need parent links? What is the ordering policy here? Without using all nodes in the tree for data, it seems like a waste of space and time (just use a hash, array, etc?). Your example of storing three strings shows 4 leaf nodes instead of 3. Please clarify your intent.
– ggorlen
Nov 23 '18 at 17:08
1
The tree in Example 2 is not complete ... a complete binary tree has all levels filled except maybe the last one
– mettleap
Nov 23 '18 at 17:15
@ggorlen The tree is actually supposed to be a MerkleTree. So the leaves and the InnerNodes will both have hashes. If TreeNode is the superclass of the two, you can work directly with the TreeNode class and avoid duplicated code. I simpflified it to adress the recursive reation of the tree structure. I want to create the complete (but empty[no Strings in leaves yet]) binary tree (since 4 leaves for 3 strings). I would like to implement a toString() method later which traverses the tree, so you will need a parent link. Also to generate the root hash, you'll need the link to parent.
– kiaora
Nov 23 '18 at 17:51
That helps clarify, thanks.
– ggorlen
Nov 23 '18 at 18:30
That's a lot of questions. Maybe stick to one at a time, because this will attract incomplete answers.
– jdv
Nov 24 '18 at 15:12
add a comment |
0
0
0
1
Purpose:
I would like to create a full and complete binary tree, which saves a String value in its leaves, recursively.
Example 1:
Let's say you want to save two Strings in your tree. So you will need a root and two leaves.
* <- root node
/
v0 v1 <- leaves
Example 2:
Let's say you want to save three Strings in your tree. So you will need a root, two inner Nodes but four leaves, so the tree is still complete.
* <- root node
/
+ + <- inner node
/
/
/ /
v0 v1 v2 v3 <- leaves
Math trickery:
Its fairly straightforward to calculate the specs for the binary tree.
Height: ⌈log2 expectedNumOfStrings⌉
double height = Math.log(expectedNumOfStrings) / Math.log(2);
int roundedHeight = (int) Math.ceil(height);
Number of leaves: 2Height
int numOfLeaves = (int) Math.pow(2, roundedHeight);
Number of inner Nodes: 2h − 1
int numOfInnerNodes = (int) (Math.pow(2, roundedHeight)-1)
Implementation:
Let's implement a couple of classes for this binary tree. We'll need a BinaryTree class.
/**
* Create a complete binary tree recursively depending on the expected leaves.
*/
public class BinaryTree {
private InnerNode root;
private LeafNode current;
public BinaryTree(int expectedNumOfStrings) {
//sets root node
this.root = new InnerNode();
//set inner nodes
root.createInnerNodes(expectedNumOfStrings);
//set leaves
root.createLeaves(expectedNumOfStrings);
//The way things are now the tree isn't created in one go.
//I'll have to traverse it again for the leaves.
}
}
All elements of the tree share a link to the parent (for the root it's null). Let's create a class TreeNode:
public class TreeNode {
private TreeNode parent;
}
Now let's create InnerNode and LeafNode which just extends TreeNode.
public class InnerNode extends TreeNode {
private BinaryTree left;
private BinaryTree right;
//used to set the root node
public InnerNode() {
super.parent = null;
this.left=null;
this.right=null;
}
public InnerNode(InnerNode parent) {
super.parent= parent;
}
public TreeNode createInnerNodes(int expectedValues) {
//recursive magic happens here. But how?
}
}
and
public class LeafNode extends TreeNode {
private String data;
public LeafNode(InnerNode parent) {
super.parent= parent;
}
public LeafNode createLeaves(int numOfLeaves) {
//recursive magic happens here again. But how?
}
}
Questions and Problems
- I want to keep the classes as separated as they are and I want to set the Tree up in one go. How to I set up
InnerNodesandLeavesat the "same" time?
InnerNode leftandInnerNode rightare private so I can only access them from withinInnerNode. But how do I deal with the leaves then? Can I just pass the root Node though toInnerNode/Leavesin a method?- What is best used for the recursion? Height or Number of corresponding nodes? Or something else entirely?
- How do you set the left and right pointer? I mean the objects to which they point don't exist yet, do they?
- Am I on the right track? /o
java recursion binary-tree
asked Nov 23 '18 at 16:56
kiaora
226
Purpose:
I would like to create a full and complete binary tree, which saves a String value in its leaves, recursively.
Example 1:
Let's say you want to save two Strings in your tree. So you will need a root and two leaves.
* <- root node
/
v0 v1 <- leaves
Example 2:
Let's say you want to save three Strings in your tree. So you will need a root, two inner Nodes but four leaves, so the tree is still complete.
* <- root node
/
+ + <- inner node
/
/
/ /
v0 v1 v2 v3 <- leaves
Math trickery:
Its fairly straightforward to calculate the specs for the binary tree.
Height: ⌈log2 expectedNumOfStrings⌉
double height = Math.log(expectedNumOfStrings) / Math.log(2);
int roundedHeight = (int) Math.ceil(height);
Number of leaves: 2Height
int numOfLeaves = (int) Math.pow(2, roundedHeight);
Number of inner Nodes: 2h − 1
int numOfInnerNodes = (int) (Math.pow(2, roundedHeight)-1)
Implementation:
Let's implement a couple of classes for this binary tree. We'll need a BinaryTree class.
/**
* Create a complete binary tree recursively depending on the expected leaves.
*/
public class BinaryTree {
private InnerNode root;
private LeafNode current;
public BinaryTree(int expectedNumOfStrings) {
//sets root node
this.root = new InnerNode();
//set inner nodes
root.createInnerNodes(expectedNumOfStrings);
//set leaves
root.createLeaves(expectedNumOfStrings);
//The way things are now the tree isn't created in one go.
//I'll have to traverse it again for the leaves.
}
}
All elements of the tree share a link to the parent (for the root it's null). Let's create a class TreeNode:
public class TreeNode {
private TreeNode parent;
}
Now let's create InnerNode and LeafNode which just extends TreeNode.
public class InnerNode extends TreeNode {
private BinaryTree left;
private BinaryTree right;
//used to set the root node
public InnerNode() {
super.parent = null;
this.left=null;
this.right=null;
}
public InnerNode(InnerNode parent) {
super.parent= parent;
}
public TreeNode createInnerNodes(int expectedValues) {
//recursive magic happens here. But how?
}
}
and
public class LeafNode extends TreeNode {
private String data;
public LeafNode(InnerNode parent) {
super.parent= parent;
}
public LeafNode createLeaves(int numOfLeaves) {
//recursive magic happens here again. But how?
}
}
Questions and Problems
- I want to keep the classes as separated as they are and I want to set the Tree up in one go. How to I set up
InnerNodesandLeavesat the "same" time?
InnerNode leftandInnerNode rightare private so I can only access them from withinInnerNode. But how do I deal with the leaves then? Can I just pass the root Node though toInnerNode/Leavesin a method?- What is best used for the recursion? Height or Number of corresponding nodes? Or something else entirely?
- How do you set the left and right pointer? I mean the objects to which they point don't exist yet, do they?
- Am I on the right track? /o
java recursion binary-tree
java recursion binary-tree
asked Nov 23 '18 at 16:56
kiaora
226
asked Nov 23 '18 at 16:56
kiaora
226
edited Nov 24 '18 at 13:50
asked Nov 23 '18 at 16:56
kiaora
226
asked Nov 23 '18 at 16:56
kiaora
226
asked Nov 23 '18 at 16:56
kiaora
226
226
I feel like having separate classes for root, inner and leaf nodes is a bit over-engineered. Since trees are recursive, it makes good sense to only have one node class. May I also ask why you're only storing data in leaves? Why do you need parent links? What is the ordering policy here? Without using all nodes in the tree for data, it seems like a waste of space and time (just use a hash, array, etc?). Your example of storing three strings shows 4 leaf nodes instead of 3. Please clarify your intent.
– ggorlen
Nov 23 '18 at 17:08
1
The tree in Example 2 is not complete ... a complete binary tree has all levels filled except maybe the last one
– mettleap
Nov 23 '18 at 17:15
@ggorlen The tree is actually supposed to be a MerkleTree. So the leaves and the InnerNodes will both have hashes. If TreeNode is the superclass of the two, you can work directly with the TreeNode class and avoid duplicated code. I simpflified it to adress the recursive reation of the tree structure. I want to create the complete (but empty[no Strings in leaves yet]) binary tree (since 4 leaves for 3 strings). I would like to implement a toString() method later which traverses the tree, so you will need a parent link. Also to generate the root hash, you'll need the link to parent.
– kiaora
Nov 23 '18 at 17:51
That helps clarify, thanks.
– ggorlen
Nov 23 '18 at 18:30
That's a lot of questions. Maybe stick to one at a time, because this will attract incomplete answers.
– jdv
Nov 24 '18 at 15:12
add a comment |
I feel like having separate classes for root, inner and leaf nodes is a bit over-engineered. Since trees are recursive, it makes good sense to only have one node class. May I also ask why you're only storing data in leaves? Why do you need parent links? What is the ordering policy here? Without using all nodes in the tree for data, it seems like a waste of space and time (just use a hash, array, etc?). Your example of storing three strings shows 4 leaf nodes instead of 3. Please clarify your intent.
– ggorlen
Nov 23 '18 at 17:08
1
The tree in Example 2 is not complete ... a complete binary tree has all levels filled except maybe the last one
– mettleap
Nov 23 '18 at 17:15
@ggorlen The tree is actually supposed to be a MerkleTree. So the leaves and the InnerNodes will both have hashes. If TreeNode is the superclass of the two, you can work directly with the TreeNode class and avoid duplicated code. I simpflified it to adress the recursive reation of the tree structure. I want to create the complete (but empty[no Strings in leaves yet]) binary tree (since 4 leaves for 3 strings). I would like to implement a toString() method later which traverses the tree, so you will need a parent link. Also to generate the root hash, you'll need the link to parent.
– kiaora
Nov 23 '18 at 17:51
That helps clarify, thanks.
– ggorlen
Nov 23 '18 at 18:30
That's a lot of questions. Maybe stick to one at a time, because this will attract incomplete answers.
– jdv
Nov 24 '18 at 15:12
I feel like having separate classes for root, inner and leaf nodes is a bit over-engineered. Since trees are recursive, it makes good sense to only have one node class. May I also ask why you're only storing data in leaves? Why do you need parent links? What is the ordering policy here? Without using all nodes in the tree for data, it seems like a waste of space and time (just use a hash, array, etc?). Your example of storing three strings shows 4 leaf nodes instead of 3. Please clarify your intent.
– ggorlen
Nov 23 '18 at 17:08
I feel like having separate classes for root, inner and leaf nodes is a bit over-engineered. Since trees are recursive, it makes good sense to only have one node class. May I also ask why you're only storing data in leaves? Why do you need parent links? What is the ordering policy here? Without using all nodes in the tree for data, it seems like a waste of space and time (just use a hash, array, etc?). Your example of storing three strings shows 4 leaf nodes instead of 3. Please clarify your intent.
– ggorlen
Nov 23 '18 at 17:08
1
1
The tree in Example 2 is not complete ... a complete binary tree has all levels filled except maybe the last one
– mettleap
Nov 23 '18 at 17:15
The tree in Example 2 is not complete ... a complete binary tree has all levels filled except maybe the last one
– mettleap
Nov 23 '18 at 17:15
@ggorlen The tree is actually supposed to be a MerkleTree. So the leaves and the InnerNodes will both have hashes. If TreeNode is the superclass of the two, you can work directly with the TreeNode class and avoid duplicated code. I simpflified it to adress the recursive reation of the tree structure. I want to create the complete (but empty[no Strings in leaves yet]) binary tree (since 4 leaves for 3 strings). I would like to implement a toString() method later which traverses the tree, so you will need a parent link. Also to generate the root hash, you'll need the link to parent.
– kiaora
Nov 23 '18 at 17:51
@ggorlen The tree is actually supposed to be a MerkleTree. So the leaves and the InnerNodes will both have hashes. If TreeNode is the superclass of the two, you can work directly with the TreeNode class and avoid duplicated code. I simpflified it to adress the recursive reation of the tree structure. I want to create the complete (but empty[no Strings in leaves yet]) binary tree (since 4 leaves for 3 strings). I would like to implement a toString() method later which traverses the tree, so you will need a parent link. Also to generate the root hash, you'll need the link to parent.
– kiaora
Nov 23 '18 at 17:51
That helps clarify, thanks.
– ggorlen
Nov 23 '18 at 18:30
That helps clarify, thanks.
– ggorlen
Nov 23 '18 at 18:30
That's a lot of questions. Maybe stick to one at a time, because this will attract incomplete answers.
– jdv
Nov 24 '18 at 15:12
That's a lot of questions. Maybe stick to one at a time, because this will attract incomplete answers.
– jdv
Nov 24 '18 at 15:12
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53450481%2fcreate-a-full-and-complete-binary-tree-recursively%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53450481%2fcreate-a-full-and-complete-binary-tree-recursively%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
I feel like having separate classes for root, inner and leaf nodes is a bit over-engineered. Since trees are recursive, it makes good sense to only have one node class. May I also ask why you're only storing data in leaves? Why do you need parent links? What is the ordering policy here? Without using all nodes in the tree for data, it seems like a waste of space and time (just use a hash, array, etc?). Your example of storing three strings shows 4 leaf nodes instead of 3. Please clarify your intent.
– ggorlen
Nov 23 '18 at 17:08
1
The tree in Example 2 is not complete ... a complete binary tree has all levels filled except maybe the last one
– mettleap
Nov 23 '18 at 17:15
@ggorlen The tree is actually supposed to be a MerkleTree. So the leaves and the InnerNodes will both have hashes. If TreeNode is the superclass of the two, you can work directly with the TreeNode class and avoid duplicated code. I simpflified it to adress the recursive reation of the tree structure. I want to create the complete (but empty[no Strings in leaves yet]) binary tree (since 4 leaves for 3 strings). I would like to implement a toString() method later which traverses the tree, so you will need a parent link. Also to generate the root hash, you'll need the link to parent.
– kiaora
Nov 23 '18 at 17:51
That helps clarify, thanks.
– ggorlen
Nov 23 '18 at 18:30
That's a lot of questions. Maybe stick to one at a time, because this will attract incomplete answers.
– jdv
Nov 24 '18 at 15:12