Balanced Binary Tree Algorithm

The Balanced Binary Tree Algorithm is a fundamental computer science concept that deals with the organization and manipulation of data structures called balanced binary trees. Binary trees are hierarchical structures consisting of nodes, with each node having at most two child nodes, arranged in a way that the value of the left child node is lesser than or equal to the parent node, and the value of the right child node is greater than or equal to the parent node. A balanced binary tree, on the other hand, is a binary tree in which the depth (i.e., the length of the longest path from the root node to a leaf node) of the left and right subtrees of every node differs by at most one. This property ensures that the tree is roughly evenly balanced, which is important for maintaining optimal performance in various operations such as searching, insertion, and deletion. The Balanced Binary Tree Algorithm is a collection of techniques and strategies for managing the balance of a binary tree, primarily focusing on maintaining the tree's balance during insertion and deletion operations. There are several different types of balanced binary trees, such as the AVL tree, Red-Black tree, and B-trees, each with their own unique balancing algorithms. The main idea behind these algorithms is to perform rotations and reorganization of nodes in the tree when an imbalance is detected, ensuring that the tree remains balanced and its operations run efficiently. With a balanced binary tree, the time complexity of search, insertion, and deletion operations is reduced to O(log n), where n is the number of nodes in the tree, providing a significant performance improvement over unbalanced binary trees, which can have time complexity as high as O(n).
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        bool flag = true;
        dfs(root, flag);
        return flag;
    }
    int dfs(TreeNode* node, bool& flag) {
        if (node == NULL)
            return 0;
        int lf = 1 + dfs(node->left, flag);
        int rt = 1 + dfs(node->right, flag);
        
        if (abs(rt - lf) > 1)
            flag = false;
        return max(lf, rt);
    }
};

LANGUAGE:

DARK MODE: