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
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.
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.
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.
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.
diana_falkowska In python2:
def insert(r, val): if r == None: r = Node(val) elif (val < r.data): r.left = insert(r.left, val) elif (val > r.data): r.right = insert(r.right, val) return r
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
siddharthgupta51 where is python for this challenge
denalilumma Why no Python?
GlukAlex besides Python I want Scala or Node.js
mdicioccio25 Here is my solution with recursion. The key is checking if the root exists, and if it does you check if data is greater than or less than the root's data. If greater call the function with the right child and data. If it is less than call the function with the left child and data. Otherwise the correct leaf has been reached and the data will be added to a new Node and appended to the left if less than or right if greater than.
def insert(root, data): if root is None: return Node(data) if data < root.data: if root.left is not None: insert(root.left, data) else: root.left = Node(data) else: if root.right is not None: insert(root.right, data) else: root.right = Node(data) return root
cztaylor Nice! Here is my more concise version. No need to check if r.left (or r.right) is None and then create a new Node if it is None. If it is None, then you can call the recursive function the new Node will be returned in the next layer of the recursion
def insert(r,val): if not r: return Node(val) elif val < r.data: r.left = insert(r.left,val) else: r.right = insert(r.right,val) return r
Sort 210 Discussions, By:
Please Login in order to post a comment