JavaScript: Balanced binary tree

Last update: 18 Mar 23:20
0
Students

The feature of the binary tree structure gives a good increase in efficiency when searching for the desired value. The binary tree must be balanced to make this happen. This means that any node of the tree must be constructed such that the sum of the nodes in the left and right subtrees is roughly equal.

Node.js

Implement the isBalanced() method that checks the tree for balance. It returns true if each node's left and right subtrees include no more than two different nodes. Otherwise, the method should return false.

Balanced tree

Balanced binary search tree

Unbalanced tree

Unbalanced binary search tree

In node 5, the number of nodes in the left subtree is 4, and in the right — 1. The difference is 3. This is more than the maximum allowable difference according to the condition of the problem (2).

Examples

const tree1 = new Node(4,
  new Node(3,
    new Node(2)));

tree1.isBalanced(); // true

const tree2 = new Node(4,
  new Node(3,
    new Node(2,
      new Node(1))));

tree2.isBalanced(); // false

For full access to the challenge you need a professional subscription.

A professional subscription will give you full access to all Hexlet courses, projects and lifetime access to the theory of lessons learned. You can cancel your subscription at any time.

Get access
130
courses
1000
exercises
2000+
hours of theory
3200
tests