Make Binary Tree return some kind of flag when inserting a duplicate
in
Programming Questions
•
11 months ago
I'm making a Binary Search tree for the first time. So far it seems to work, but I would like to be able to test if I am inserting a duplicate element. Right now it simply doesn't insert anything if the tree already contained the element and prints a message saying "Duplicate". Can I make this return a boolean so I could test if it didn't insert anything?
I realize that I could use contains() first, but I'd prefer insert() to return a boolean. Also, as this is the first time I'm writing a Binary Search tree any pointers on improvements are welcome.
- BTree tree = new BTree();
- void setup() {
- size(400, 400);
- tree.insert(4);
- tree.insert(8);
- tree.insert(8);
- tree.insert(2);
- tree.insert(3);
- println(tree.contains(2));
- }
- void draw() {
- }
- class BTree {
- Node root;
- BTree() {
- root = null;
- }
- boolean contains(int in) {
- return contains(in, root);
- }
- boolean contains(int in, Node curr) {
- if (curr == null) return false;
- if (in < curr.val) return contains(in, curr.left);
- else if (in > curr.val) return contains(in, curr.right);
- else return true;
- }
- boolean isEmpty() {
- return root == null;
- }
- void insert(int in) {
- root = insert(in, root);
- }
- Node insert(int in, Node curr) {
- if (curr == null) return new Node(in, null, null);
- if (in < curr.val) curr.left = insert(in, curr.left);
- else if (in > curr.val) curr.right = insert(in, curr.right);
- else println("Duplicate");
- return curr;
- }
- void makeEmpty() {
- root = null;
- }
- }
- class Node {
- int val;
- Node left;
- Node right;
- Node(int v) {
- val = v;
- left = null;
- right = null;
- }
- Node(int v, Node l, Node r) {
- val = v;
- left = l;
- right = r;
- }
- }
1