DEV Community

Cover image for Binary Tree 1.0
Ivan Livshits
Ivan Livshits

Posted on • Updated on

Binary Tree 1.0

What is binary tree and when we could use them?

A binary tree is a fundamental tree data structure that consists of nodes connected in a hierarchical manner. Each node in a binary tree can have at most two children: a left child and a right child. The topmost node in the tree is called the root, while the nodes with no children are known as leaves.

The binary tree structure can be visualized as a branching structure, with the root at the top and the leaves at the bottom. Each node can have zero, one, or two child nodes, forming a recursive structure. This means that each child node can, in turn, have its own left and right children, creating a hierarchical arrangement.

Binary trees find applications in various fields of computer science. One common use is in data storage and retrieval, where binary trees can be used for efficient searching and organizing data. For example, binary search trees utilize the binary tree structure along with the ordering property to enable fast searching operations.

Binary trees are also useful in expression evaluation, where they can represent mathematical expressions in a hierarchical manner. By traversing the binary tree using appropriate algorithms, expressions can be evaluated efficiently.

In network routing, binary trees can be employed to organize and navigate network nodes. The tree structure allows for efficient routing decisions by determining the next node to traverse based on the binary tree's branching structure.

Moreover, binary trees serve as a foundation for implementing various algorithms, including sorting algorithms like heapsort and binary search algorithms. They can also be extended to more complex tree structures such as AVL trees, red-black trees, and B-trees to address specific requirements in terms of balancing, efficiency, and space optimization.

In summary, a binary tree is a versatile data structure used in a wide range of applications in computer science, including data storage, expression evaluation, network routing, and algorithm implementation. Its hierarchical nature and recursive properties make it a powerful tool for organizing and manipulating data efficiently.

Binary tree image


Unique keys in Binary Trees

Every node in a binary search tree has a unique key value, meaning the tree cannot contain two nodes with identical keys. This uniqueness allows for precise node identification and aids in locating specific values within the tree.

Typically, the value we stipulate becomes the node's key. The type of key used varies depending on the task at hand:

Integer Key: When using integers as keys, you can straightforwardly assign an integer value to each node. This could be values from an array, element indices, or any other unique numeral.

String Key: If the keys are in string format, you can either use the strings themselves or their hashed values as keys. Utilizing hashed string values can expedite comparison and key lookup operations, particularly in large trees.

Custom Class Key: If you're using an object-oriented programming language, you can create a custom class to define its own comparison methods for keys. This involves either implementing comparison methods or defining an interface for key comparison.

Here are simple examples of each of the mentioned trees using TypeScript. The codes do not include all possible operations, such as deletion, search, etc., but they provide a basic understanding of the data structures.

Binary Search Tree (BST)

Here, key is used to determine the position of a node in the tree, and value is the data stored in the node.

class Node {
  key: number;
  value: number;
  left: Node | null;
  right: Node | null;

  constructor(key: number, value: number) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  root: Node | null;

  constructor() {
    this.root = null;
  }

  insert(key: number, value: number) {
    let newNode = new Node(key, value);

    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node: Node, newNode: Node) {
    if (newNode.key < node.key) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

Red-Black Tree (RBT)

Just like in BST, key is used to determine the position of a node in the tree, and value is the data stored in the node. Additionally, each node has a color property.

// Due to complexity, here's a simplified example without all operations.

enum Color {
  RED,
  BLACK
}

class Node {
  key: number;
  value: number;
  color: Color;
  left: Node | null;
  right: Node | null;

  constructor(key: number, value: number, color: Color) {
    this.key = key;
    this.value = value;
    this.color = color;
    this.left = null;
    this.right = null;
  }
}

class RBT {
  root: Node | null;

  constructor() {
    this.root = null;
  }

  // Simple insertion function without tree balancing
  insert(key: number, value: number) {
    let newNode = new Node(key, value, Color.RED);

    if (this.root === null) {
      this.root = newNode;
    } else {
      // insert node as per BST rules, without implementing node recoloring
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

AVL Tree

Here as well, key is used to determine the position of a node in the tree, and value is the data stored in the node. Additionally, each node has a height property which is used during tree balancing.

// Simplified example without balancing the tree and all necessary operations.

class Node {
  key: number;
  value: number;
  height: number;
  left: Node | null;
  right: Node | null;

  constructor(key: number, value: number) {
    this.key = key;
    this.value = value;
    this.height = 1; // leaf height is always 1
    this.left = null;
    this.right = null;
  }
}

class AVL {
  root: Node | null;

  constructor() {
    this.root = null;
  }

  insert(key: number, value: number) {
    let newNode = new Node(key, value);

    if (this.root === null) {
      this.root = newNode;
    } else {
      // Inserting node according to BST rules, without implementing balancing
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

Please note that these examples are highly simplified. A full implementation of each of these trees would be significantly more complex and include many other operations and details.

Types of Binary Tree based on the number of children

Following are the types of Binary Tree based on the number of children:

  1. Full Binary Tree;
  2. Degenerate Binary Tree;
  3. Skewed Binary Tree;

Full Binary Tree

A full binary tree is a type of binary tree where every node has either zero or two children. In other words, in a full binary tree, all nodes, except for the leaf nodes, have exactly two children.

The structure of a full binary tree is such that each internal node (non-leaf node) has exactly two child nodes. This property distinguishes a full binary tree from other types of binary trees where nodes may have different numbers of children.

By definition, leaf nodes in a full binary tree are the nodes that do not have any children. These nodes are the endpoints of the tree structure.

The concept of a full binary tree is commonly used in various algorithms and data structures. It provides a balanced and efficient representation for certain applications. For example, heap data structures, such as the binary heap, often utilize a complete binary tree, which is a type of full binary tree, to maintain the heap property efficiently.

To summarize, a full binary tree is a binary tree where all internal nodes, except for the leaf nodes, have exactly two children. This tree structure ensures a balanced and efficient representation in certain algorithms and data structures.

Full binary tree

Degenerate (or pathological) tree

A degenerate or pathological tree is a type of tree where every internal node has only one child. In other words, all nodes, except for the leaf nodes, have a single child either to the left or to the right.

The structure of a degenerate tree resembles a linked list more than a typical tree. This is because there is a linear progression from one node to the next, with each node having only one child.

In terms of performance, degenerate trees behave similarly to linked lists. Traversing or searching through a degenerate tree requires visiting each node in a linear manner, resulting in a time complexity of O(n), where n is the number of nodes in the tree. This is because there are no branching points or multiple choices at each level to efficiently narrow down the search space.

Due to their lack of branching and imbalance, degenerate trees are considered inefficient for many tree-based algorithms and operations. They do not offer the advantages of balanced trees, such as binary search trees or AVL trees, which provide logarithmic time complexity for searching, inserting, and deleting operations.

However, it's worth noting that in certain scenarios, degenerate trees may have specific use cases or applications. For example, they can be used to represent ordered lists or sequences, where maintaining a linear order is more important than efficient searching or tree-based operations.

In summary, a degenerate or pathological tree is a type of tree where each internal node has only one child. These trees exhibit similar performance characteristics to linked lists, resulting in inefficient operations compared to balanced trees. While degenerate trees may have specific use cases, they are generally not optimal for most tree-based algorithms and operations.

Degenerate (or pathological) tree

Skewed Binary Tree
A skewed binary tree is a special type of pathological or degenerate tree where the tree is heavily biased towards either the left or right subtree. This bias means that one side of the tree is dominant, while the other side has very few or no nodes.

There are two variations of skewed binary trees: left-skewed binary trees and right-skewed binary trees.

  • Left-skewed binary tree: In a left-skewed binary tree, each node, except for the leaf nodes, has only a left child. This means that as we traverse the tree from the root to the leaves, we only encounter left children.

  • Right-skewed binary tree: In a right-skewed binary tree, each node, except for the leaf nodes, has only a right child. As we traverse the tree from the root to the leaves, we encounter only right children.

Skewed binary trees exhibit performance characteristics similar to linked lists or linear data structures. Traversing or searching through a skewed binary tree requires visiting each node in a linear manner, resulting in a time complexity of O(n), where n is the number of nodes in the tree.

Due to their imbalanced structure, skewed binary trees are generally not suitable for efficient searching, inserting, or deleting operations. They lack the branching and balanced properties of more balanced tree structures, such as AVL trees or red-black trees.

However, skewed binary trees may find specific applications or use cases. For example, they can be used to represent ordered sequences or lists, where maintaining a specific order is more important than efficient tree-based operations.

In summary, a skewed binary tree is a pathological or degenerate tree where one side of the tree is heavily dominant, either with only left children (left-skewed binary tree) or only right children (right-skewed binary tree). Skewed binary trees generally exhibit linear performance characteristics and are not optimal for most tree-based operations.

Skewed binary tree


Types of Binary Tree on the basis of the completion of levels

Following are the types of Binary Tree based on the basis of the completion of levels:

  1. Complete Binary Tree;
  2. Perfect Binary Tree;
  3. Balanced Binary Tree;

Complete Binary Tree

A complete binary tree is a specific type of binary tree with the following characteristics:

  • Every level, except possibly the last level, is completely filled with nodes. This means that all levels are populated with nodes from left to right, without any missing nodes in between.

  • All leaf nodes (nodes with no children) are positioned towards the left side of the tree. In other words, the leftmost leaf nodes of each level are filled first, followed by the nodes to their right.

  • The last level of the tree may not be completely filled. If there are any missing nodes in the last level, they must be positioned to the left, leaving no gaps on the right side of the level.

It's important to note that a complete binary tree does not have to be a full binary tree. In a complete binary tree, the last level may not be completely filled, unlike a full binary tree where every node has either zero or two children.

The concept of a complete binary tree is often used in efficient array-based representations of binary trees. By using an array and following specific indexing rules, a complete binary tree can be stored compactly without any wasted space.

Complete binary trees have practical applications in various algorithms and data structures. For example, they are utilized in heap data structures such as the binary heap, where the complete binary tree property allows for efficient heap operations like insertion and deletion.

In summary, a complete binary tree is a type of binary tree where every level, except possibly the last level, is fully populated, leaf nodes lean towards the left, and the last level may not be completely filled. This concept provides a balanced and efficient structure for certain applications and array-based representations of binary trees.

Complete Binary Tree

Perfect Binary Tree

A perfect binary tree is a specific type of binary tree that satisfies two main conditions:

  • Every internal node in the tree has exactly two children. This means that all non-leaf nodes have two child nodes.

  • All leaf nodes (nodes with no children) are positioned at the same level or depth. In other words, every path from the root to a leaf node has the same length.

In a perfect binary tree, the number of leaf nodes is equal to the number of internal nodes plus one. This relationship holds true because each internal node has two children, except for the last level, where all leaf nodes are present.

A practical example of a perfect binary tree is the representation of ancestors in a family tree. Starting with a person as the root, each level represents the parents of the previous generation, and the tree grows upward. In this structure, each person has exactly two parents, and all leaf nodes (individuals with no parents) are at the same generational level.

Perfect binary trees have a balanced and symmetric structure. Due to their regularity, they allow for efficient indexing and searching algorithms. Additionally, perfect binary trees are used as a basis for other binary tree variations, such as complete binary trees and balanced binary trees.

In summary, a perfect binary tree is a type of binary tree in which all internal nodes have two children, and all leaf nodes are positioned at the same level. This structure ensures a balanced and symmetrical tree, and it has practical applications in indexing, searching, and as a foundation for other binary tree variants.

Perfect Binary Tree

Balanced Binary Tree

A balanced binary tree is a type of binary tree in which the heights of its left and right subtrees are kept within a certain limit to ensure the tree remains relatively balanced. This balance is maintained by adhering to specific conditions or properties, which vary depending on the type of balanced binary tree.

For example, an AVL tree is a self-balancing binary search tree that maintains a maximum height difference of 1 between its left and right subtrees. This balance is achieved by performing rotations and rebalancing operations when necessary during insertions and deletions. As a result, AVL trees provide efficient search, insertion, and deletion operations with a time complexity of O(log n), where n is the number of nodes.

Another example is the red-black tree, which is another type of self-balancing binary search tree. Red-black trees ensure balance by enforcing specific rules, such as the requirement that the number of black nodes on every root-to-leaf path is the same and that no adjacent nodes are colored red. By maintaining these properties, red-black trees also guarantee a logarithmic height, enabling efficient operations on the tree.

Balanced binary search trees, such as AVL trees and red-black trees, offer significant performance advantages compared to unbalanced binary trees. With their logarithmic height, these trees ensure that the time complexity of search, insertion, and deletion operations remains at O(log n), making them well-suited for large datasets and frequent operations.

In summary, balanced binary trees, such as AVL trees and red-black trees, maintain a logarithmic height by enforcing specific conditions or properties. This balance allows for efficient search, insert, and delete operations with a time complexity of O(log n). Balanced binary search trees provide performance advantages over unbalanced trees, making them suitable for various applications that require efficient data storage and retrieval.

Balanced binary tree


Other special types of trees

Based on the values of nodes, binary trees can be categorized into several important types:

  1. Binary Search Tree;
  2. AVL Tree;
  3. Red Black Tree;
  4. B Tree;
  5. B+ Tree;
  6. Segment Tree;

In practice, Binary Search Trees, AVL Trees, and Red-Black Trees are commonly encountered and extensively used due to their balanced nature and efficient operations. However, B trees, B+ trees, and segment trees have their specific applications and advantages in scenarios involving large-scale data storage, indexing, and range-based queries.

Binary Search Tree

A binary search tree (BST) is a specific type of binary tree that follows certain properties:

Ordering Property: In a binary search tree, for every node, the values of all nodes in its left subtree are less than its own value, and the values of all nodes in its right subtree are greater than its own value. This property allows for efficient searching by narrowing down the search space based on the comparison of values.

Unique Key Property: Each node in a binary search tree has a unique key value. This ensures that no two nodes in the tree have the same key, enabling unambiguous identification of nodes.

The presence of the ordering and unique key properties in a binary search tree allows for efficient search, insertion, and deletion operations. The ordering property facilitates faster lookup by directing the search path based on the comparison of values, reducing the search space at each step.

It's important to note that while a binary search tree is a specific type of binary tree, not all binary trees are binary search trees. In a binary search tree, the values are organized in a specific order, whereas a binary tree can have nodes arranged without any particular ordering or constraints.

In summary, a binary tree is a general tree structure where nodes can have at most two children, while a binary search tree is a specific type of binary tree that maintains an ordered structure based on the values of its nodes. The ordering property of a binary search tree allows for efficient searching, insertion, and deletion operations by leveraging the comparisons of node values.

Binary Search Tree

AVL Tree

The AVL tree, named after its inventors Adelson-Velsky and Landis, is a type of self-balancing binary search tree (BST). It is designed to maintain balance within the tree by ensuring that the difference between the heights of the left and right subtrees of every node is no more than one.

In other words, in an AVL tree, the heights of the left and right subtrees of each node are kept in balance, with a maximum difference of one. If the balance condition is violated after an insertion or deletion operation, the tree undergoes rotations to restore balance.

The self-balancing property of AVL trees helps to prevent degeneration and ensures that the tree remains relatively balanced. By maintaining balance, AVL trees provide efficient search, insertion, and deletion operations with a time complexity of O(log n), where n is the number of nodes in the tree.

The concept of AVL trees is widely used in various applications that require efficient searching and dynamic updates, such as database systems, compiler implementations, and data structure libraries.

In summary, an AVL tree is a self-balancing binary search tree where the height difference between the left and right subtrees of each node is restricted to a maximum of one. This balance property ensures efficient operations and prevents the tree from becoming highly imbalanced or degenerate.

AVL Tree

Red Black Tree

A red-black tree is a type of self-balancing binary search tree in which each node contains an additional bit that represents its color, typically red or black. This coloring scheme is used to maintain balance during insertions and deletions.

The red-black tree is designed to ensure that the tree remains relatively balanced, although not perfectly balanced. By maintaining specific properties and rules associated with the colors of nodes, red-black trees can achieve efficient searching and keep the tree's height close to logarithmic, approximately O(log n), where n is the total number of elements in the tree.

The balancing rules of red-black trees include:

  • Red-Black Property: Every node is either red or black.
  • Root Property: The root node is always black.
  • Red Property: Every red node must have two black children.
  • Depth Property: For each node, every path from that node to its descendant leaves contains an equal number of black nodes. By adhering to these rules, red-black trees maintain balance and ensure that the longest path from the root to any leaf is not more than twice the length of the shortest path. This balance property provides efficient search, insertion, and deletion operations in comparison to unbalanced binary search trees.

Red-black trees find application in various domains, including data storage, indexing, and database systems. They are widely used to implement balanced and efficient data structures, as well as in algorithms that require efficient searching and dynamic updates.

In summary, a red-black tree is a self-balancing binary search tree where each node contains a color bit (red or black) to maintain balance during insertions and deletions. Although the balance is not perfect, the red-black tree achieves logarithmic searching time by adhering to specific properties and rules associated with node colors. This makes red-black trees suitable for applications that require efficient data storage and retrieval.

Red Black Tree

B - Tree

A B-tree is a self-balancing tree data structure that is designed for efficient access, insertion, and deletion of data items. It is widely used in databases and file systems due to its ability to handle large amounts of data effectively. A B-tree is characterized by a fixed maximum degree or order, which determines the maximum number of child nodes a parent node can have.

In a B-tree, each node can have multiple child nodes and multiple keys. The keys serve as indices for locating and organizing data items. The structure of a B-tree allows for efficient search operations by leveraging the keys to navigate through the tree and locate the desired data item.

One of the main advantages of a B-tree is its ability to maintain balance, ensuring that the height of the tree remains relatively small and providing efficient operations. By adhering to balancing rules, such as maintaining a minimum number of keys in each node and redistributing keys during insertions and deletions, the B-tree achieves balanced and efficient access to data.

The B-tree's balanced structure enables fast search operations with a time complexity of approximately O(log n), where n represents the number of data items stored in the tree. This logarithmic time complexity makes B-trees suitable for scenarios involving large-scale data storage and retrieval.

In summary, a B-tree is a self-balancing tree data structure that allows efficient access, insertion, and deletion operations. It is commonly used in databases and file systems due to its ability to handle large amounts of data and maintain balance. B-trees provide efficient search operations with a time complexity of approximately O(log n) and are well-suited for applications involving substantial data storage and retrieval needs.

B Tree

B+ - Tree

A B+ tree is a specialized variant of the B-tree that is specifically optimized for use in file systems and databases. While similar to a B-tree in terms of its fixed maximum degree and efficient access, insertion, and deletion operations, the B+ tree has some key distinctions.

In a B+ tree, all data items are stored in the leaf nodes of the tree. This design choice ensures that the internal nodes of the B+ tree solely contain keys for indexing and locating the data items. By separating the data items from the internal nodes, the B+ tree achieves several advantages.

One major advantage is improved search performance. Since the leaf nodes exclusively store the data items, searching within the B+ tree only requires traversing the leaf nodes, resulting in faster searches compared to traditional B-trees. Additionally, the leaf nodes of a B+ tree are typically linked together in a linked list, allowing for efficient sequential access and range queries.

Another benefit of storing data items solely in the leaf nodes is simplified range queries and data range scans. With the leaf nodes forming a linked list, scanning through the data items in a specific order becomes more efficient, making B+ trees well-suited for applications that require efficient range-based operations.

By combining the benefits of efficient searching, sequential access, and simplified range queries, B+ trees have become a popular choice for file systems and databases. They provide an efficient and balanced data structure for organizing and managing large volumes of data, ensuring fast access and optimized performance.

In summary, a B+ tree is a specialized variant of the B-tree optimized for file systems and databases. It stores data items exclusively in leaf nodes while using internal nodes for indexing. The design of B+ trees enables efficient search operations, fast sequential access, and simplified range queries, making them well-suited for applications involving file systems and databases.

B plus tree

Segment Tree

In computer science, a Segment Tree, also known as a statistic tree, is a tree-based data structure used to store and retrieve information about intervals or segments. Its primary purpose is to efficiently answer queries regarding which stored segments contain a given point.

The Segment Tree is considered a static structure, meaning that it is typically built once and cannot be modified afterward. It is designed to handle scenarios where intervals are known in advance and there is a need for efficient interval-based querying.

A similar data structure to the Segment Tree is the Interval Tree, which also deals with interval-based operations. While the Segment Tree focuses on queries related to point containment within intervals, the Interval Tree provides additional functionality, such as finding overlapping intervals or performing range queries.

By employing a hierarchical tree structure, the Segment Tree allows for efficient operations on intervals. It subdivides the space into smaller segments and stores information about these segments in the tree nodes. The information can be precomputed and aggregated to facilitate quick querying based on the specific requirements.

Segment Trees find applications in various fields such as computational geometry, databases, and algorithm design. They are commonly used to solve problems involving interval-based queries, such as range sum queries, range minimum/maximum queries, and identifying intervals containing specific points.

In summary, a Segment Tree is a tree-based data structure used for efficient storage and querying of interval-based information. It provides a static framework for handling interval-related operations, particularly determining which stored segments contain a given point. Segment Trees are widely used in computational geometry, databases, and other areas requiring efficient interval-based querying and analysis.

Segment tree


Small task about Binary Tree from coding interview

In a recent coding interview, I encountered an interesting task that involved searching in a binary tree.

During the interview, I was given the challenge of implementing a search algorithm to find a specific value within a binary tree. The task required me to traverse the tree and determine whether the desired value was present.

Write a function which takes a binary tree and a number as an input. 
It should find in the tree and output minimum number that is greater than given.
Example of tree:
            10
          /    \
        5       15
      /  |      /  \
     2   7    12   17
n = 16
expected output is 17
Enter fullscreen mode Exit fullscreen mode

I was required to not only design a solution but also write the actual working code and test it. To tackle the task effectively, I started by considering the model for the binary tree structure.

Since each node in a binary tree consists of a value and references to its left and right children, I decided to create a base class to represent the tree. This class served as a blueprint for creating instances of nodes in the binary tree.

By modeling the tree structure using a class, I could easily create and manipulate nodes, set their values, and establish the appropriate connections between parent and child nodes. This allowed me to build and traverse the tree effectively in my solution.

To ensure the correctness of my code, I implemented a series of test cases. I carefully designed test scenarios that covered various aspects of the problem, including searching for existing values, searching for non-existent values, and handling edge cases such as empty trees.

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
Enter fullscreen mode Exit fullscreen mode

Great! Once I have modeled my binary tree using the base class, the next step in the process is to mock the tree based on the requirements of the given task.

const root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(2);
root.left.right = new Node(7);
root.right.left = new Node(12);
root.right.right = new Node(17);
Enter fullscreen mode Exit fullscreen mode

To solve the tree traversal problem, I initially considered two common approaches: recursion and using a loop. For the sake of clarity, I decided to start with the loop-based approach.

In this approach, the first step was to create a copy of the original tree passed into the function. This copy ensured that we did not modify the original tree during the traversal process. Additionally, I set the initial minimum value that we aimed to find within the tree.

let currentTree = tree;
let minValue = number;
Enter fullscreen mode Exit fullscreen mode

Now, let's proceed with building the loop-based traversal algorithm. The main condition for the loop will be the existence of a tree to traverse. Within the loop, we will handle two scenarios based on the value of the current node and the desired minimum value.

If the value of the current node is greater than the desired minimum value, we will update our minimum value to the value of the current node and move to the left branch of the tree. This is because we know that the numbers in the left subtree will be smaller than the parent node.

On the other hand, if the value of the current node is less than the desired minimum value, we will move to the right branch of the tree. This way, we will explore larger numbers in our search for the minimum value.

By following this simple and intuitive algorithm, we can effectively traverse the tree and identify the minimum value within it.

while ( currentTree ) {
    if (currentTree.value > number )
        { 
            minValue = currentTree.value;
            currentTree = currentTree.left;
        } else {
            currentTree = currentTree.right;
        }
    }
Enter fullscreen mode Exit fullscreen mode

Now, let's determine the return value of our function based on the defined conditions. If the minimum value found during the traversal is not equal to the desired number, we will return this minimum value. However, if the minimum value is equal to the desired number, we will return null.

return minValue !== number ? minValue : null;
Enter fullscreen mode Exit fullscreen mode

The task has been successfully solved and the code is functioning correctly!

~ node test.js
  n = 16, expected output = 17
  result: 17
  n = 1, expected output = 2
  result: 2
  n = 17, expected output = null
  result: null
Enter fullscreen mode Exit fullscreen mode

Solution in Kotlin

class Node {
    var value: Int? = null
    var left: Node? = null
    var right: Node? = null

    companion object {
    fun add(node: Node?, value: Int): Node {
        if (node == null)
            return this.createNode(value)

        if (node.value != null && value < node.value!!)
            node.left = add(node.left, value);
        else if (node.value != null && value > node.value!!)
            node.right = add(node.right, value);

        return node
    }

    fun createNode(item: Int): Node {
        val temp = Node()
        temp.value = item
        temp.right = null
        temp.left = null
        return temp
    }

    fun findMinForN(node: Node?, target: Int): Int {
        if (node?.left == null && node?.right == null && node?.value == null) {
            return -1;
        }

        if ((node.value!! >= target && node.left == null) ||
            ((node.value!! >= target && node.left?.value!! < target))
        ) {
            return if (node.value == target) -1 else node.value!!
        }

        return if (node.value != null && node.value!! <= target)
            findMinForN(node.right, target)
        else
            findMinForN(node.left, target)
        }
    }

    override fun toString(): String {
        return "Node(value=$value, left=$left, right=$right)"
    }

}

fun main() {
    var root: Node? = null
    root = Node.add(root, 10)
    root = Node.add(root, 5)
    root = Node.add(root, 15)
    root = Node.add(root, 2)
    root = Node.add(root, 7)
    root = Node.add(root, 12)
    root = Node.add(root, 17)

    println(Node.findMinForN(root, 16))
}
Enter fullscreen mode Exit fullscreen mode

Top comments (5)

Collapse
 
bodiia profile image
Vadim Bodianskii

Great article, comrade. My understanding of tree data structures has improved.

Collapse
 
bretbernhoft profile image
Bret Bernhoft

Good work with the if-statements, those are fun to use in my opinion. I also appreciate the time you took to create code samples. Having the JavaScript to look at makes the whole article much easier to digest.

Collapse
 
anshidhaneef profile image
AnshidHaneef

Appreciate 👏

Collapse
 
philipjohnbasile profile image
Philip John Basile

Great article!

Collapse
 
berhram profile image
Daniíl Pechorin

Thx for clarifying a topic