Loop for inserting a node into a binary search tree
up vote
2
down vote
favorite
I am trying to implement binary search tree. One method which I am trying to implement in the most efficient and stylish way is node insertion.
I am under the impression that while (true) is a bad practice, correct?
while (true){
if(n <currentNode.data){
if (currentNode.left == null){
currentNode.left = new node(n);
break;
}else{
currentNode = currentNode.left;
}
}else
if (currentNode.right == null) {
currentNode.right = new node(n);
break;
} else{
currentNode = currentNode.right;
}
}
and here is the whole code:
package graph;
public class BSearchTree {
private node head = null;
public BSearchTree(int entries){
for (int a : entries){
insert(a);
}
}
public void insert(int n){
if (head == null){
head = new node(n);
return;
}
node currentNode = head;
while (true){
if(n <currentNode.data){
if (currentNode.left == null){
currentNode.left = new node(n);
break;
}else{
currentNode = currentNode.left;
}
}else
if (currentNode.right == null) {
currentNode.right = new node(n);
break;
} else{
currentNode = currentNode.right;
}
}
}
public static void main(String args) {
BSearchTree bst = new BSearchTree(new int{2,4,1,5});
System.out.println(bst.toString());
}
private class node {
int data = -1;
node left = null;
node right = null;
public node(int n){
data = n;
}
}
}
java tree binary-search
edited Nov 9 '17 at 18:01
200_success
127k15149412
asked Nov 9 '17 at 17:38
Waterfr Villa
1111
bumped to the homepage by Community♦ 28 mins ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
up vote
2
down vote
favorite
I am trying to implement binary search tree. One method which I am trying to implement in the most efficient and stylish way is node insertion.
I am under the impression that while (true) is a bad practice, correct?
while (true){
if(n <currentNode.data){
if (currentNode.left == null){
currentNode.left = new node(n);
break;
}else{
currentNode = currentNode.left;
}
}else
if (currentNode.right == null) {
currentNode.right = new node(n);
break;
} else{
currentNode = currentNode.right;
}
}
and here is the whole code:
package graph;
public class BSearchTree {
private node head = null;
public BSearchTree(int entries){
for (int a : entries){
insert(a);
}
}
public void insert(int n){
if (head == null){
head = new node(n);
return;
}
node currentNode = head;
while (true){
if(n <currentNode.data){
if (currentNode.left == null){
currentNode.left = new node(n);
break;
}else{
currentNode = currentNode.left;
}
}else
if (currentNode.right == null) {
currentNode.right = new node(n);
break;
} else{
currentNode = currentNode.right;
}
}
}
public static void main(String args) {
BSearchTree bst = new BSearchTree(new int{2,4,1,5});
System.out.println(bst.toString());
}
private class node {
int data = -1;
node left = null;
node right = null;
public node(int n){
data = n;
}
}
}
java tree binary-search
edited Nov 9 '17 at 18:01
200_success
127k15149412
asked Nov 9 '17 at 17:38
Waterfr Villa
1111
bumped to the homepage by Community♦ 28 mins ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
while(true)just causes an infinite loop, is that what you want to do? If so, to me anyway, that's the simplest way to do it.
– user152925
Nov 9 '17 at 17:45
@no, I am processing a finite stream in a seemingly infinite fashion, I dont want that.
– Waterfr Villa
Nov 9 '17 at 17:55
I wouldn't say awhile (true) ... breakis necessarily bad practice. It can be nice thendo while, and you don't always want to declare a boolean for no reason. Some considerbreaka form of goto (some also pre-function end returns gotos, but it's really just context-dependent), but sometimes it's clearer and more efficient than any alternatives.
– Graham
Nov 5 at 5:05
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I am trying to implement binary search tree. One method which I am trying to implement in the most efficient and stylish way is node insertion.
I am under the impression that while (true) is a bad practice, correct?
while (true){
if(n <currentNode.data){
if (currentNode.left == null){
currentNode.left = new node(n);
break;
}else{
currentNode = currentNode.left;
}
}else
if (currentNode.right == null) {
currentNode.right = new node(n);
break;
} else{
currentNode = currentNode.right;
}
}
and here is the whole code:
package graph;
public class BSearchTree {
private node head = null;
public BSearchTree(int entries){
for (int a : entries){
insert(a);
}
}
public void insert(int n){
if (head == null){
head = new node(n);
return;
}
node currentNode = head;
while (true){
if(n <currentNode.data){
if (currentNode.left == null){
currentNode.left = new node(n);
break;
}else{
currentNode = currentNode.left;
}
}else
if (currentNode.right == null) {
currentNode.right = new node(n);
break;
} else{
currentNode = currentNode.right;
}
}
}
public static void main(String args) {
BSearchTree bst = new BSearchTree(new int{2,4,1,5});
System.out.println(bst.toString());
}
private class node {
int data = -1;
node left = null;
node right = null;
public node(int n){
data = n;
}
}
}
java tree binary-search
edited Nov 9 '17 at 18:01
200_success
127k15149412
asked Nov 9 '17 at 17:38
Waterfr Villa
1111
I am trying to implement binary search tree. One method which I am trying to implement in the most efficient and stylish way is node insertion.
I am under the impression that while (true) is a bad practice, correct?
while (true){
if(n <currentNode.data){
if (currentNode.left == null){
currentNode.left = new node(n);
break;
}else{
currentNode = currentNode.left;
}
}else
if (currentNode.right == null) {
currentNode.right = new node(n);
break;
} else{
currentNode = currentNode.right;
}
}
and here is the whole code:
package graph;
public class BSearchTree {
private node head = null;
public BSearchTree(int entries){
for (int a : entries){
insert(a);
}
}
public void insert(int n){
if (head == null){
head = new node(n);
return;
}
node currentNode = head;
while (true){
if(n <currentNode.data){
if (currentNode.left == null){
currentNode.left = new node(n);
break;
}else{
currentNode = currentNode.left;
}
}else
if (currentNode.right == null) {
currentNode.right = new node(n);
break;
} else{
currentNode = currentNode.right;
}
}
}
public static void main(String args) {
BSearchTree bst = new BSearchTree(new int{2,4,1,5});
System.out.println(bst.toString());
}
private class node {
int data = -1;
node left = null;
node right = null;
public node(int n){
data = n;
}
}
}
java tree binary-search
java tree binary-search
edited Nov 9 '17 at 18:01
200_success
127k15149412
asked Nov 9 '17 at 17:38
Waterfr Villa
1111
edited Nov 9 '17 at 18:01
200_success
127k15149412
asked Nov 9 '17 at 17:38
Waterfr Villa
1111
edited Nov 9 '17 at 18:01
200_success
127k15149412
edited Nov 9 '17 at 18:01
200_success
127k15149412
edited Nov 9 '17 at 18:01
200_success
127k15149412
127k15149412
asked Nov 9 '17 at 17:38
Waterfr Villa
1111
asked Nov 9 '17 at 17:38
Waterfr Villa
1111
asked Nov 9 '17 at 17:38
Waterfr Villa
1111
1111
bumped to the homepage by Community♦ 28 mins ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
bumped to the homepage by Community♦ 28 mins ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
while(true)just causes an infinite loop, is that what you want to do? If so, to me anyway, that's the simplest way to do it.
– user152925
Nov 9 '17 at 17:45
@no, I am processing a finite stream in a seemingly infinite fashion, I dont want that.
– Waterfr Villa
Nov 9 '17 at 17:55
I wouldn't say awhile (true) ... breakis necessarily bad practice. It can be nice thendo while, and you don't always want to declare a boolean for no reason. Some considerbreaka form of goto (some also pre-function end returns gotos, but it's really just context-dependent), but sometimes it's clearer and more efficient than any alternatives.
– Graham
Nov 5 at 5:05
add a comment |
while(true)just causes an infinite loop, is that what you want to do? If so, to me anyway, that's the simplest way to do it.
– user152925
Nov 9 '17 at 17:45
@no, I am processing a finite stream in a seemingly infinite fashion, I dont want that.
– Waterfr Villa
Nov 9 '17 at 17:55
I wouldn't say awhile (true) ... breakis necessarily bad practice. It can be nice thendo while, and you don't always want to declare a boolean for no reason. Some considerbreaka form of goto (some also pre-function end returns gotos, but it's really just context-dependent), but sometimes it's clearer and more efficient than any alternatives.
– Graham
Nov 5 at 5:05
while(true)just causes an infinite loop, is that what you want to do? If so, to me anyway, that's the simplest way to do it.– user152925
Nov 9 '17 at 17:45
while(true)just causes an infinite loop, is that what you want to do? If so, to me anyway, that's the simplest way to do it.– user152925
Nov 9 '17 at 17:45
@no, I am processing a finite stream in a seemingly infinite fashion, I dont want that.
– Waterfr Villa
Nov 9 '17 at 17:55
@no, I am processing a finite stream in a seemingly infinite fashion, I dont want that.
– Waterfr Villa
Nov 9 '17 at 17:55
I wouldn't say a
while (true) ... break is necessarily bad practice. It can be nice then do while, and you don't always want to declare a boolean for no reason. Some consider break a form of goto (some also pre-function end returns gotos, but it's really just context-dependent), but sometimes it's clearer and more efficient than any alternatives.– Graham
Nov 5 at 5:05
I wouldn't say a
while (true) ... break is necessarily bad practice. It can be nice then do while, and you don't always want to declare a boolean for no reason. Some consider break a form of goto (some also pre-function end returns gotos, but it's really just context-dependent), but sometimes it's clearer and more efficient than any alternatives.– Graham
Nov 5 at 5:05
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
(Just checking - you want your BST to be allowed to contain duplicates? That's what your current code does.)
Edit: After fixing some mistakes kindly pointed out by @vnp, here is an implementation of insert:
public void insert(int n) {
final boolean RIGHT = true;
final boolean LEFT = false;
node previousNode = null;
boolean previousDirection = LEFT; // arbitrary
node currentNode = head;
while (currentNode != null) {
previousNode = currentNode;
if (n > currentNode.data) {
currentNode = currentNode.right;
previousDirection = RIGHT;
} else {
currentNode = currentNode.left;
previousDirection = LEFT;
}
}
if (previousNode == null) {
head = new node(n);
} else if (previousDirection == LEFT) {
previousNode.left = new node(n);
} else {
previousNode.right = new node(n);
}
}
This avoids using while(true) and break; and uses more shallow if statements, which I think makes it marginally easier to follow.
answered Nov 9 '17 at 18:40
ArbitraryGenera
162
1
I don't seenode.nextdefined anywhere. There arenode.leftandnode.right.
– vnp
Nov 9 '17 at 21:28
@vnp Good point! I'm missing this. How about also storing a boolean previousDirection at each step, and using this to determine whether to go right or left? (That means declaring private final static boolean RIGHT = true; private final static boolean LEFT = false; at the start.)
– ArbitraryGenera
Nov 9 '17 at 21:37
1
Then I see no benefits (suggested implementation would be helpful). BTW, thoseRIGHTandLEFTdo not belong to the class; they are local toinsert.
– vnp
Nov 9 '17 at 21:43
@vnp thanks! I've provided an implementation - it's definitely arguable that this implementation is no better!
– ArbitraryGenera
Nov 9 '17 at 22:49
Is it also easier to understand? I mean compared to my solution?
– Waterfr Villa
Nov 10 '17 at 16:49
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
(Just checking - you want your BST to be allowed to contain duplicates? That's what your current code does.)
Edit: After fixing some mistakes kindly pointed out by @vnp, here is an implementation of insert:
public void insert(int n) {
final boolean RIGHT = true;
final boolean LEFT = false;
node previousNode = null;
boolean previousDirection = LEFT; // arbitrary
node currentNode = head;
while (currentNode != null) {
previousNode = currentNode;
if (n > currentNode.data) {
currentNode = currentNode.right;
previousDirection = RIGHT;
} else {
currentNode = currentNode.left;
previousDirection = LEFT;
}
}
if (previousNode == null) {
head = new node(n);
} else if (previousDirection == LEFT) {
previousNode.left = new node(n);
} else {
previousNode.right = new node(n);
}
}
This avoids using while(true) and break; and uses more shallow if statements, which I think makes it marginally easier to follow.
answered Nov 9 '17 at 18:40
ArbitraryGenera
162
1
I don't seenode.nextdefined anywhere. There arenode.leftandnode.right.
– vnp
Nov 9 '17 at 21:28
@vnp Good point! I'm missing this. How about also storing a boolean previousDirection at each step, and using this to determine whether to go right or left? (That means declaring private final static boolean RIGHT = true; private final static boolean LEFT = false; at the start.)
– ArbitraryGenera
Nov 9 '17 at 21:37
1
Then I see no benefits (suggested implementation would be helpful). BTW, thoseRIGHTandLEFTdo not belong to the class; they are local toinsert.
– vnp
Nov 9 '17 at 21:43
@vnp thanks! I've provided an implementation - it's definitely arguable that this implementation is no better!
– ArbitraryGenera
Nov 9 '17 at 22:49
Is it also easier to understand? I mean compared to my solution?
– Waterfr Villa
Nov 10 '17 at 16:49
add a comment |
up vote
0
down vote
(Just checking - you want your BST to be allowed to contain duplicates? That's what your current code does.)
Edit: After fixing some mistakes kindly pointed out by @vnp, here is an implementation of insert:
public void insert(int n) {
final boolean RIGHT = true;
final boolean LEFT = false;
node previousNode = null;
boolean previousDirection = LEFT; // arbitrary
node currentNode = head;
while (currentNode != null) {
previousNode = currentNode;
if (n > currentNode.data) {
currentNode = currentNode.right;
previousDirection = RIGHT;
} else {
currentNode = currentNode.left;
previousDirection = LEFT;
}
}
if (previousNode == null) {
head = new node(n);
} else if (previousDirection == LEFT) {
previousNode.left = new node(n);
} else {
previousNode.right = new node(n);
}
}
This avoids using while(true) and break; and uses more shallow if statements, which I think makes it marginally easier to follow.
answered Nov 9 '17 at 18:40
ArbitraryGenera
162
1
I don't seenode.nextdefined anywhere. There arenode.leftandnode.right.
– vnp
Nov 9 '17 at 21:28
@vnp Good point! I'm missing this. How about also storing a boolean previousDirection at each step, and using this to determine whether to go right or left? (That means declaring private final static boolean RIGHT = true; private final static boolean LEFT = false; at the start.)
– ArbitraryGenera
Nov 9 '17 at 21:37
1
Then I see no benefits (suggested implementation would be helpful). BTW, thoseRIGHTandLEFTdo not belong to the class; they are local toinsert.
– vnp
Nov 9 '17 at 21:43
@vnp thanks! I've provided an implementation - it's definitely arguable that this implementation is no better!
– ArbitraryGenera
Nov 9 '17 at 22:49
Is it also easier to understand? I mean compared to my solution?
– Waterfr Villa
Nov 10 '17 at 16:49
add a comment |
up vote
0
down vote
up vote
0
down vote
(Just checking - you want your BST to be allowed to contain duplicates? That's what your current code does.)
Edit: After fixing some mistakes kindly pointed out by @vnp, here is an implementation of insert:
public void insert(int n) {
final boolean RIGHT = true;
final boolean LEFT = false;
node previousNode = null;
boolean previousDirection = LEFT; // arbitrary
node currentNode = head;
while (currentNode != null) {
previousNode = currentNode;
if (n > currentNode.data) {
currentNode = currentNode.right;
previousDirection = RIGHT;
} else {
currentNode = currentNode.left;
previousDirection = LEFT;
}
}
if (previousNode == null) {
head = new node(n);
} else if (previousDirection == LEFT) {
previousNode.left = new node(n);
} else {
previousNode.right = new node(n);
}
}
This avoids using while(true) and break; and uses more shallow if statements, which I think makes it marginally easier to follow.
answered Nov 9 '17 at 18:40
ArbitraryGenera
162
(Just checking - you want your BST to be allowed to contain duplicates? That's what your current code does.)
Edit: After fixing some mistakes kindly pointed out by @vnp, here is an implementation of insert:
public void insert(int n) {
final boolean RIGHT = true;
final boolean LEFT = false;
node previousNode = null;
boolean previousDirection = LEFT; // arbitrary
node currentNode = head;
while (currentNode != null) {
previousNode = currentNode;
if (n > currentNode.data) {
currentNode = currentNode.right;
previousDirection = RIGHT;
} else {
currentNode = currentNode.left;
previousDirection = LEFT;
}
}
if (previousNode == null) {
head = new node(n);
} else if (previousDirection == LEFT) {
previousNode.left = new node(n);
} else {
previousNode.right = new node(n);
}
}
This avoids using while(true) and break; and uses more shallow if statements, which I think makes it marginally easier to follow.
answered Nov 9 '17 at 18:40
ArbitraryGenera
162
edited Nov 9 '17 at 22:48
answered Nov 9 '17 at 18:40
ArbitraryGenera
162
answered Nov 9 '17 at 18:40
ArbitraryGenera
162
answered Nov 9 '17 at 18:40
ArbitraryGenera
162
162
1
I don't seenode.nextdefined anywhere. There arenode.leftandnode.right.
– vnp
Nov 9 '17 at 21:28
@vnp Good point! I'm missing this. How about also storing a boolean previousDirection at each step, and using this to determine whether to go right or left? (That means declaring private final static boolean RIGHT = true; private final static boolean LEFT = false; at the start.)
– ArbitraryGenera
Nov 9 '17 at 21:37
1
Then I see no benefits (suggested implementation would be helpful). BTW, thoseRIGHTandLEFTdo not belong to the class; they are local toinsert.
– vnp
Nov 9 '17 at 21:43
@vnp thanks! I've provided an implementation - it's definitely arguable that this implementation is no better!
– ArbitraryGenera
Nov 9 '17 at 22:49
Is it also easier to understand? I mean compared to my solution?
– Waterfr Villa
Nov 10 '17 at 16:49
add a comment |
1
I don't seenode.nextdefined anywhere. There arenode.leftandnode.right.
– vnp
Nov 9 '17 at 21:28
@vnp Good point! I'm missing this. How about also storing a boolean previousDirection at each step, and using this to determine whether to go right or left? (That means declaring private final static boolean RIGHT = true; private final static boolean LEFT = false; at the start.)
– ArbitraryGenera
Nov 9 '17 at 21:37
1
Then I see no benefits (suggested implementation would be helpful). BTW, thoseRIGHTandLEFTdo not belong to the class; they are local toinsert.
– vnp
Nov 9 '17 at 21:43
@vnp thanks! I've provided an implementation - it's definitely arguable that this implementation is no better!
– ArbitraryGenera
Nov 9 '17 at 22:49
Is it also easier to understand? I mean compared to my solution?
– Waterfr Villa
Nov 10 '17 at 16:49
1
1
I don't see
node.next defined anywhere. There are node.left and node.right.– vnp
Nov 9 '17 at 21:28
I don't see
node.next defined anywhere. There are node.left and node.right.– vnp
Nov 9 '17 at 21:28
@vnp Good point! I'm missing this. How about also storing a boolean previousDirection at each step, and using this to determine whether to go right or left? (That means declaring private final static boolean RIGHT = true; private final static boolean LEFT = false; at the start.)
– ArbitraryGenera
Nov 9 '17 at 21:37
@vnp Good point! I'm missing this. How about also storing a boolean previousDirection at each step, and using this to determine whether to go right or left? (That means declaring private final static boolean RIGHT = true; private final static boolean LEFT = false; at the start.)
– ArbitraryGenera
Nov 9 '17 at 21:37
1
1
Then I see no benefits (suggested implementation would be helpful). BTW, those
RIGHT and LEFT do not belong to the class; they are local to insert.– vnp
Nov 9 '17 at 21:43
Then I see no benefits (suggested implementation would be helpful). BTW, those
RIGHT and LEFT do not belong to the class; they are local to insert.– vnp
Nov 9 '17 at 21:43
@vnp thanks! I've provided an implementation - it's definitely arguable that this implementation is no better!
– ArbitraryGenera
Nov 9 '17 at 22:49
@vnp thanks! I've provided an implementation - it's definitely arguable that this implementation is no better!
– ArbitraryGenera
Nov 9 '17 at 22:49
Is it also easier to understand? I mean compared to my solution?
– Waterfr Villa
Nov 10 '17 at 16:49
Is it also easier to understand? I mean compared to my solution?
– Waterfr Villa
Nov 10 '17 at 16:49
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Code Review Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fcodereview.stackexchange.com%2fquestions%2f180022%2floop-for-inserting-a-node-into-a-binary-search-tree%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
while(true)just causes an infinite loop, is that what you want to do? If so, to me anyway, that's the simplest way to do it.– user152925
Nov 9 '17 at 17:45
@no, I am processing a finite stream in a seemingly infinite fashion, I dont want that.
– Waterfr Villa
Nov 9 '17 at 17:55
I wouldn't say a
while (true) ... breakis necessarily bad practice. It can be nice thendo while, and you don't always want to declare a boolean for no reason. Some considerbreaka form of goto (some also pre-function end returns gotos, but it's really just context-dependent), but sometimes it's clearer and more efficient than any alternatives.– Graham
Nov 5 at 5:05