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;
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; }
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; }
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; }
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
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.
craig_stevenson Can we assume this BST contains no duplicates?
lichcat According to the definition , there is no duplicates (same key value node) in BST. See https://en.wikipedia.org/wiki/Binary_search_tree.
I think you should consider duplicate inputs, but the result BST should not contain duplicates.
maximshen I think this problem assumes TreeSet in java, so no duplicates. Anyway, it should be more clearly defined in the problem.
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
apansfds node * insert(node * root, int value) { if(!root) { root = new 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; }
brkykrlk In the recursive calls of insert why do we have to assign their return value to the root->left and root-> right ? Wouldn't it work if we just call the function?
auld_brian Then the node that you just tried to insert won't be attached to the tree. For all other nodes it's a don't care as it returns the value root->left/right is already set to.
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
justin_menga Python solution:
def insert(r,val): if r is None: r = Node(val) elif r.data > val: r.left = insert(r.left, val) elif r.data < val: r.right = insert(r.right, val) return r
fhuang52 used same code and put in class BinaryTree, but kept getting "NameError: name 'insert' is not defined" error...confused.
NEGA_tive same here buddy. Did you found a solution
wdodman It's the types. Insert is defined in the Binary SearchTree class and .lef/.rigth are defined in the Node class. I tried making each .left/.right into a BinarySearchTree and then making each root into a Node but then it fails on preOrder when they need to be BinarySearchTrees again.
siddharthgupta51 where is python for this challenge
denalilumma Why no Python?
GlukAlex besides Python I want Scala or Node.js
Sort 285 Discussions, By:
Please Login in order to post a comment