deepak_nitraipur static Node Insert(Node root,int value) {
if(root==null) { Node node=new Node(); node.data=value; node.left=null; node.right=null; root=node; } else if(root.data>value) root.left=Insert(root.left,value); else if(root.data<value) root.right=Insert(root.right,value); return root; }
jonmcclung And here I was with 100 lines of code trying to solve it without recursion... Thanks for the idea! (Just looked over it really quickly and then did the same idea in C++)
ZachPerkitny node * insert(node * root, int value) { node * r = root; node *rs = NULL; node *ls = NULL; if(root == NULL){ root = new node; root->data = value; root->left = root->right = NULL; } while(r != NULL){ if(value < r->data){ if(r->left == NULL) ls = r; r = r->left; } else if(value > r->data) { if(r->right == NULL) rs = r; r = r->right; } } r = new node; r->data = value; r->left = r->right = NULL; if(ls != NULL) ls->left = r; if(rs != NULL) rs->right = r; return root; }
You can do it without recursion pretty easily.
jonmcclung showoff ;)
omike1900 thank you for you share, you can solve it that code below, it can save some code (my code is written by Java).
There is not need variable
rsandlsstatic Node Insert(Node root, int value) { Node newNode = new Node(); newNode.data = value; if (root == null) { return newNode; } Node iterator = root; while (iterator != null) { if (value < iterator.data) { if (iterator.left == null) { iterator.left = newNode; break; } iterator = iterator.left; } else { if (iterator.right == null) { iterator.right = newNode; break; } iterator = iterator.right; } } return root; }
lokesh1729 Thank you for sharing... I did with two pointers and thought we can't do with one... Even I have generalized like LinkedLists have one node, we need one pointer, BST have two nodes, we need two pointers :P
jakewilson801 Love this solution thanks for sharing
jaind7775 thanks for sharing
kapploneon public static Node insert(Node root,int data) { Node current = root; if(current == null){ return new Node(data); } while((current.left != null && current.data > data) || (current.right != null && current.data < data)){ if(current.data < data){ current = current.right; }else{ current = current.left; } } Node temp = new Node(data); if(current.data < data){ current.right = temp; }else{ current.left = temp; } return root; }raghav14 if(root == null) return new Node(data); Node toInsert = new Node(data), temp = root; while(true) { if(toInsert.data <= temp.data) { if(temp.left != null) temp = temp.left; else { temp.left = toInsert; break; } } else if(toInsert.data > temp.data) { if(temp.right != null) temp = temp.right; else { temp.right = toInsert; break; } } } return root;
4N118020373 dfgdgsg
kshtjkmar Thanks! Clean solution. :)
areebaibrar03 please help me with the diplay code aswell.
[deleted] Thanks for the above solution.
saharsh_singh Mostly similar Java solution:
static Node Insert(Node root,int value) { Node insert = new Node(); insert.data = value; if(root == null) { return insert; } Node current = null; Node next = root; while(next != null) { current = next; next = (current.data < value) ? current.right : current.left; } if(current.data < value) { current.right = insert; } else { current.left = insert; } return root; }
ashutoshghimire Luckily I completed in 20 lines
Node current=root; Node last=root; while(current!=null){ last=current; if(current.data<value)current=current.right; else current=current.left; } Node temp=new Node(); temp.data=value; if(root==null)return temp; if(last.data<value)last.right=temp; else last.left=temp; return root;
srihitha_tangud1 Node x = new Node(); x.data=value; if(root==null){ root = x; } else{ Node prev=null; while(root!=null){ prev=root; if(value<=root.data){ root=root.left; } else root=root.right; } if(value>prev.data) prev.right=x; else prev.left=x; } return root;
Hey, my code is almost same as your code, but I am getting Null Pointer Exception.Can you help me out with this?
NandiChaurasiya Hey! after while loop, your root ptr becomes null, and insert() returns NULL pointer. So, take another pointer to traverse in while loop.
adityasuman2025 haaa haa
NandiChaurasiya It is possible in 16 lines without recursion also. Just look at it once.
node * insert(node * root, int value) { node* newnode = new node; newnode->data = value; newnode->left = NULL; newnode->right = NULL; if(root == NULL) root = newnode; node *temp = root; while(temp->left && value < temp->data){ temp = temp->left;} while(temp->right && value > temp->data){ temp = temp->right;} while(temp->left && value < temp->data){ temp = temp->left;} if(value > temp->data) temp->right = newnode; if(value < temp->data) temp->left = newnode; return root; }
diasdenny7 how about these values .will the code work for value 560.
1000 / / 500 \ \ 600 / / 550 \ \ 575
NikolaTECH Use "nullptr" instead of "null". Why don't you use pointers?
Node node=new Node();This is dynamic memory allocation. You should later delete allocated memory (like this =>
delete node;if you don't want memory leak.jonmcclung Are you sure that applies to Java, or were you thinking of C++?
maximshen He used Java
etayluz [deleted]
john400 Why is the test Case 5 failing when I don't use static in the method name? Why are you using static here?Can you please explain.:)
omike1900 Beacause this method is provided by Hackerrank, you can't modify anything except method's body.
gmi10 test case five is the an empty tree, make sure your solution works when root == NULL
RohithYerramilli what is the reason for static and test case 5??
AdHominem You dont need to assign null to the leaves of a newly created node. They are null by default.
avardar note that following lines are unnecesary in Java:
node.left=null; node.right=null;
NormalMan thank you for your share. :)
brijeshthakur Where are we adding whether the new node will be the child node of existing node? We are simply traversing till the end of a tree and adding a new node which doesn't have parent? Am I missing something?
JakeHerb You don't acrually have to create a separate node named Node. You can just say: root = new Node(); root.data = value; return root;
And it'll work just fine.
Akshita_Sood does this code not change the root pointer which has to be returned at the end?
ratingkabanda you can skip null part, just node.data will do
static Node Insert(Node root,int value) { if(root == null){ Node node = new Node(); node.data = value; root = node; } else{ if(value < root.data){ root.left = Insert(root.left, value); } else if(value > root.data) root.right = Insert(root.right, value); } return root; }
kostova74 it shows compile error
reasonet Python solution:
def insert(r,val): if r is None: r = Node('') r.data = val elif val < r.data: if r.left is None: r.left = Node('') r.left.data = val else: insert(r.left, val) else: if r.right is None: r.right = Node('') r.right.data = val else: insert(r.right, val) return r
lpal1 Can you please explain why do we need the quotes inside Node('') when creating a new node?
singleheart Node(val) suffices because the constructor assigns val to self.data
akratimittal18 why we are taking Insert(root.left,value) value in root.left...anybody please help.
sprksh_j It's calling function recursively.
alexander_reed Can you explain why you alter the root.right and root.left fields? It seems as if you are continuously writing over them as you iterate down the tree.
sprksh_j Hey, no. if and only if node is Null, it is creating a node there as required in the question. and in the next line, it sets the value of node. node.data.
liyaguang2003 node * insert(node * root, int value) { if(root == NULL) { node* node; node->data = value; node->left = NULL; node->right =NULL; root = node; } else if(value>root->data) { root->right = insert(root->right,value); } else if(valuedata) { root->left = insert(root->left,value); }
return root; }
What am i doing wrong here? it keeps failing.
BansheeGhoul No need to get any value from the Insert while on recurson .. ie
else if (root.data>value) Insert(root.left,value); else if (root.dataAlso works fine.
Pheonixevolution thanks for your idea!
1234surajshawkol [deleted]stellhawk1 i dont understand how you are adding nodes if root.left or root.right are NULL.
heres my solution in cpp can anyone please explain me how to do this without checking the null condition in left or right.
Node * insert(Node * root, int data) { if(!root) return new Node(data); if(data < root->data){ if(root->left) insert(root->left,data); else root->left = new Node(data); } else if(data > root->data){ if(root->right) insert(root->right,data); else root->right = new Node(data); } return root; }sarathy_v_krish1 C++ solution (without recursion) :
Node * insert(Node * root, int data) { if (!root) return new Node(data); Node* base=root, *prev; while(base) { prev=base; if (data<base->data) base=base->left; else base=base->right; } if (prev->data<data) prev->right = new Node(data); else prev->left = new Node(data); return root; }
andreyv_moshes Nitpick:
Node's constructorNode(int data)initializes.leftand.righttonullso those two lines are unneeded.
jatinshravan node * insert(node * root, int value) { if (root == NULL) { root = (node *)malloc(sizeof(node)); root->data = value; return root; } if (value < root->data) { root->left = insert(root->left, value); } else { root->right = insert(root->right, value); } return root; }My solution
rahulrajbatheja sir...i am a beginner and i have a little doubt
i.e why are we returning root at last line...it is of no use
avidor_gershon Iterative Python solution:
def insert(self, val): if self.root == None: self.root = Node(val) root = self.root while True: if val > root.info: if root.right: root = root.right else: root.right = Node(val) break elif val < root.info: if root.left: root = root.left else: root.left = Node(val) break else: break
garethhkm2023 I know this comment is a year old, but in python you're recommended to use
is Noneinstead of== None:)ssaurabhh Just wanted to understand that in the while loop, if I replace every "root" with "self.root" and remove the line "root = self.root" then why isn't the code working?
hgrantham If you open up the classes above the method we are writing, you will see that self is a BinarySearchTree object and not a Node object. If you traverse through self.root instead of root, you are actually assigning new values to the whole tree.
The line "root = self.root" essentially pulls the top node out of the tree so we can traverse through the nodes in the while loop. It would have been clearer to use "current = self.root" instead because after the first traversal we are not actually at root anymore.
waggledans In Java need to specify constructor for Node. I used Node(value) first (it makes sense to have one like this) but after compile error changed to the default one new Node(). Anyway, constructor should be documented. Otherwise, cheers, good warmup question.
walshbre While I initially tried Node(value) as well, technically speaking the problem does implicitely document that Node() is the expected constructor.
From the problem definition,
/* Node is defined as : class Node int data; Node left; Node right; */In Java, a class definition lacking a constructor definition automatically takes on the Default Constructor. Since there is no constructor defined here, we can assume the Default Constructor will be used.
maximshen In java, default constructor like NewClass() without any parameters is given for free (by default).
EugeneLymar If no constructor is specified, Java will auto generate a default constructor.
dlima_david Recursive:
def insertion(self, cur, val): if not cur: cur = Node(val) elif cur.info > val: cur.left = self.insertion(cur.left, val) else: cur.right = self.insertion(cur.right, val) return cur def insert(self, val): if not self.root: self.root = Node(val) else: self.insertion(self.root, val)
Iterative:
def insert(self, val): cur = self.root if not cur: self.root = Node(val) return self.root while cur: if cur.info > val: if cur.left: cur = cur.left else: cur.left = Node(val) break else: if cur.right: cur = cur.right else: cur.right = Node(val) break return self.root
Sort 370 Discussions, By:
Please Login in order to post a comment