2
$\begingroup$

In a Binary Tree, can two nodes have the same value? For example:

     3
    / \
   4   4
  / \
 1   2

They are two different nodes, but they have the same value. Here is code:

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}
const r = new TreeNode(3);
r.left = new TreeNode(4);
r.right = new TreeNode(4);
r.left.left = new TreeNode(1);
$\endgroup$
1
  • 2
    $\begingroup$ A binary tree is just a tree where each node has at most two children. I’m assuming you’re referring to a binary search tree? $\endgroup$ Commented Mar 4, 2020 at 3:41

2 Answers 2

3
$\begingroup$

If you say "binary tree", my answer is " yes", since binary tree to me only says: A tree of nodes that only have at most 3 edges, of which two (binary) are pointing in the same direction (to tree leafs).

If you mean a "binary search tree", my answer is "no", since a search tree does not have any advantage in allowing duplicates, since SEARCHING for ONE value in a BST can only result in ONE value, not in two or more. Since BST search is a deterministic algorithm, one of the two mentioned duplicates will never be found and hence is totally useless. Inserting a duplicate in a BST must be skipped since its position in tree is already occupied.

$\endgroup$
1
$\begingroup$

In Binary search trees, the order of nodes are as: $leftnode<parentnode<rightnode$. So, your code will always run into error if both left and right of a parent node is same.

Please go through the following links, for more: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap13.htm https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture8.pdf

$\endgroup$
2
  • $\begingroup$ It is important to note that the ordering can be $left\leq parent < right$ or $left < parent \leq right$ $\endgroup$ Commented Mar 4, 2020 at 3:45
  • $\begingroup$ Your first link is about Binary Search Tree. I think that's probably a special kind of binary tree. PDF files are hard to read and use. I think they're not appropriate for the web. I'm not sure if LeetCode is wrong or your are wrong, but leetcode has a lot of binary tree examples that don't match your leftnode < parentnode < rightnode rule. $\endgroup$
    – Garrett
    Commented Mar 4, 2020 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.