Using Recursion to Insert Values Into a Sorted Binary Tree

Hi! I hope you are well.

I have been playing around with sorted binary trees recently.

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nod…


This content originally appeared on DEV Community and was authored by

Hi! I hope you are well.

I have been playing around with sorted binary trees recently.

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree.

My favorite part about binary trees is using recursion to travel down the nodes.

For the insert() method of my tree. I do 2 things

  1. I check if the tree is empty if so I add the node.

  2. I create a recursive function to travel down the tree and eventually add the new node if it hits the end of the branch (no more nodes)

Let's get cracking!

First part = check if the list is empty and if it is add a new node as the root and return 

// node class for reference 
class Node {
  constructor(value){
    this.value = value;
    this.left = null;
    this.right = null
  }
}

Still with me?

Cool! so here's the fun part

    this.count++;
    //recursive call
    const searchTree = node => {
      // less than
      if (value < node.value) {
        if (!node.left) {
          node.left = newNode;
        } else {
          searchTree(node.left)
        }
      greater than
      } else if (value > node.value) {
        if (!node.right) {
          node.right = newNode;
        } else {
          searchTree(node.right);
        }
      }
    }
    //start of recursive call
    searchTree(this.root)

  }

Let's

We have the following tree


            31
        30
    20      29
10 
    5  
        4

We want add 27

1st. we check if it is empty (it's not)
2nd we start the recursive call with the root (10)

first call

if (27 < 10) ....false!

goes to else if (27 > 10) ...true!

inside of else if

if (!10.right) false!!!
else {calls the recursive function but with 20}

this continues till it hits 29 at which

if (27 < 29) ...true!
if (!node.right)....TRUE!!!!!
ok! we're done!

node.right = newNode;

What do you think?

Did you enjoy this post?

Or did I get something wrong?

Feel free to contact me using my website or in the comments section below.

Have a fantastic day!


This content originally appeared on DEV Community and was authored by


Print Share Comment Cite Upload Translate Updates
APA

| Sciencx (2022-02-14T14:10:05+00:00) Using Recursion to Insert Values Into a Sorted Binary Tree. Retrieved from https://www.scien.cx/2022/02/14/using-recursion-to-insert-values-into-a-sorted-binary-tree/

MLA
" » Using Recursion to Insert Values Into a Sorted Binary Tree." | Sciencx - Monday February 14, 2022, https://www.scien.cx/2022/02/14/using-recursion-to-insert-values-into-a-sorted-binary-tree/
HARVARD
| Sciencx Monday February 14, 2022 » Using Recursion to Insert Values Into a Sorted Binary Tree., viewed ,<https://www.scien.cx/2022/02/14/using-recursion-to-insert-values-into-a-sorted-binary-tree/>
VANCOUVER
| Sciencx - » Using Recursion to Insert Values Into a Sorted Binary Tree. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2022/02/14/using-recursion-to-insert-values-into-a-sorted-binary-tree/
CHICAGO
" » Using Recursion to Insert Values Into a Sorted Binary Tree." | Sciencx - Accessed . https://www.scien.cx/2022/02/14/using-recursion-to-insert-values-into-a-sorted-binary-tree/
IEEE
" » Using Recursion to Insert Values Into a Sorted Binary Tree." | Sciencx [Online]. Available: https://www.scien.cx/2022/02/14/using-recursion-to-insert-values-into-a-sorted-binary-tree/. [Accessed: ]
rf:citation
» Using Recursion to Insert Values Into a Sorted Binary Tree | | Sciencx | https://www.scien.cx/2022/02/14/using-recursion-to-insert-values-into-a-sorted-binary-tree/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts