The Algorithm Design Manual (3rd) Exercise Solution 'E3-15 and E-3-17'

Table of Contents

Introduction
Repository
Exercise
- Question
  - 3-15
  - 3-17
- Solution

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise

Question

3-15

Describe an $O(n)$ -time algorithm that takes an n-node binary search tree and constructs an equivalent height-balanced binary search tree. In a heightbalanced binary search tree, the difference between the height of the left and right subtrees of every node is never more than 1.

3-17

Give an $O(n)$ algorithm that determines whether a given n-node binary tree is height-balanced (see Problem 3-15).

Solution

3-15

Convert the original tree into a sorted array.

Pick a median value of the array and create a tree-node. Create a subtree using range of the array from the minimum index to median index -1 and attach the subtree to tree-node as left child. Similarly, create a subtree from median index +1 to maximum index and attach as right child.

For each median index, we call the routine recursively at most n times (except the case the routine ends at first check of the length of part of array.)

So, the time complexity is O(n).

3-17

Check if each tree is balanced by comparing both depths of left subtree and right subtree.

Each tree is passed just once, so the time complexity is O(n).

Code

c++ code.

#include <cassert>
#include <concepts>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <vector>

template <std::totally_ordered T>
class Binary_search_tree {
   private:
    struct tree {
        T item;
        std::shared_ptr<tree> parent;
        std::shared_ptr<tree> left;
        std::shared_ptr<tree> right;
    };
    using p_tree = std::shared_ptr<tree>;
    p_tree root;
    p_tree tree_min{nullptr};
    int size{0};

    bool check_balanced_impl(p_tree p_root) const {
        T curr{};
        bool undefined_val{true};
        auto helper{[&](auto helper, p_tree tree) -> bool {
            if (!tree) return true;
            if (!helper(helper, tree->left)) return false;
            if (undefined_val) {
                undefined_val = false;
            } else if (tree->item < curr)
                return false;
            curr = tree->item;
            return helper(helper, tree->right);
        }};
        return helper(helper, p_root);
    }

    /*
    Check if each tree is balanced by comparing both depths of
    left subtree and right subtree.

    Each tree is passed just once, so the time complexity is O(n).
    */
    bool check_height_balanced_impl(p_tree p_root) const {
        struct Helper_result {
            bool is_valid;
            int height{0};
        };

        const auto helper{
            [](const auto helper, const p_tree tree) -> const Helper_result {
                if (!tree) return {true, 0};
                Helper_result left_result{helper(helper, tree->left)};
                if (!left_result.is_valid) return {false};
                Helper_result right_result{helper(helper, tree->right)};
                if (!right_result.is_valid) return {false};

                if (1 < std::abs(left_result.height - right_result.height)) {
                    return {false};
                }
                return {true,
                        std::max(left_result.height, right_result.height) + 1};
            }};
        return helper(helper, p_root).is_valid;
    }

   public:
    Binary_search_tree(std::initializer_list<T> list) {
        for (auto &&e : list) insert_tree(e);
    };

    /*
    Convert the original tree into a sorted array.

    Pick a median value of the array and create a tree-node.
    Create a subtree using range of the array from the minimum index
    to median index -1 and attach the subtree to tree-node as left child.
    Similarly, create a subtree from median index +1 to maximum index and
    attach as right child.

    The time complexity is O(n).
    */
    static Binary_search_tree<T> create_height_balanced(
        const Binary_search_tree<T> &bs_tree) {
        // convert into sorted array
        std::vector<T> v{bs_tree.begin(), bs_tree.end()};

        // Create tree-node by median index and
        // attach subtrees (recursion)
        Binary_search_tree<T> balanced_tree{};
        const auto helper{[&v](const auto helper, const size_t idx_min,
                               const size_t idx_max) -> p_tree {
            if (idx_max < idx_min)
                return nullptr;
            else if (idx_min == idx_max)
                return std::make_shared<tree>(v[idx_min], nullptr, nullptr,
                                              nullptr);

            size_t idx_mid{(idx_min + idx_max) / 2};
            auto tree_node{
                std::make_shared<tree>(v[idx_mid], nullptr, nullptr, nullptr)};

            p_tree left_chld{nullptr};
            if (0 < idx_mid) left_chld = helper(helper, idx_min, idx_mid - 1);
            auto right_chld{helper(helper, idx_mid + 1, idx_max)};

            tree_node->left = left_chld;
            tree_node->right = right_chld;
            if (left_chld) left_chld->parent = tree_node;
            if (right_chld) right_chld->parent = tree_node;

            return tree_node;
        }};
        balanced_tree.root = helper(helper, 0, v.size() - 1);
        balanced_tree.size = v.size();

        // set minimum tree-node for iterator
        auto tnode{balanced_tree.root};
        while (tnode->left) tnode = tnode->left;
        balanced_tree.tree_min = tnode;

        return balanced_tree;
    }

    int get_size() const { return size; };

    p_tree search_tree(T searchee) {
        auto helper{[&](auto helper, p_tree tree) -> p_tree {
            if (!tree) return nullptr;
            if (tree->item == searchee)
                return tree;
            else if (searchee < tree->item)
                return helper(helper, tree->left);
            else
                return helper(helper, tree->right);
        }};
        return helper(helper, root);
    }

    void insert_tree(T val) {
        auto helper{[&](auto helper, p_tree parent, bool is_min) -> void {
            p_tree *p_tree;
            if (val < parent->item)
                p_tree = &(parent->left);
            else {
                p_tree = &(parent->right);
                is_min = false;
            }
            if (!(*p_tree)) {
                *p_tree = std::make_shared<tree>(val, parent, nullptr, nullptr);
                if (is_min) tree_min = *p_tree;
                return;
            } else {
                helper(helper, *p_tree, is_min);
            }
        }};
        if (!root) {
            tree_min = root =
                std::make_shared<tree>(val, nullptr, nullptr, nullptr);
        } else
            helper(helper, root, true);
        ++size;
    }

    int get_max_depth() const {
        int max_d{0};
        int rest_of_elem{size};
        auto helper{[&](auto helper, p_tree tree, int curr_d) -> bool {
            // if tree is null, exit
            if (!tree) return true;
            // update the max_depth
            max_d = std::max(max_d, curr_d);
            // decrement the rest of elements
            --rest_of_elem;

            // recurse for the left and right subtrees
            if (!helper(helper, tree->left, curr_d + 1)) return false;

            // if the diff between max_degth_at_that_time and current_depth
            //  is greater than rest_of_elements, stop the
            //  sebsequent recursion
            if ((max_d - curr_d) > rest_of_elem) return false;

            if (!helper(helper, tree->right, curr_d + 1)) return false;
            return true;
        }};
        helper(helper, root, 0);
        return max_d;
    }
    bool check_balanced() const { return check_balanced_impl(root); }
    bool check_height_balanced() const {
        return check_height_balanced_impl(root);
    }

    // Iterator implementation for data to be exposed in order
    struct Iterator {
        using iterator_category = std::forward_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = value_type *;
        using reference = value_type &;

        Iterator() : current_node{nullptr} {};
        Iterator(p_tree node) : current_node{node} {};
        Iterator &operator++() {
            if (current_node->right) {
                current_node = current_node->right;
                while (current_node->left) current_node = current_node->left;
            } else {
                auto prev{current_node};
                current_node = current_node->parent;
                while (current_node) {
                    if (prev == current_node->left) break;
                    prev = current_node;
                    current_node = current_node->parent;
                }
            }
            return *this;
        }
        Iterator operator++(int) {
            Iterator it_temp{*this};
            ++(*this);
            return it_temp;
        }
        bool operator==(const Iterator &it) const {
            return this->current_node == it.current_node;
        }
        bool operator!=(const Iterator &it) const { return !(*this == it); }
        reference operator*() const { return this->current_node->item; }

       private:
        p_tree current_node;
    };
    Iterator begin() const { return Iterator(tree_min); }
    Iterator end() const { return Iterator(); }
};

int main(int argc, char const *argv[]) {
    auto test_helper{[]<typename T>(std::initializer_list<T> lst, int depth) {
        Binary_search_tree<T> bs_tree{lst};
        assert(bs_tree.get_size() == lst.size());
        Binary_search_tree<int> balanced{
            Binary_search_tree<int>::create_height_balanced(bs_tree)};
        assert(balanced.check_balanced());
        assert(balanced.get_size() == lst.size());
        assert(balanced.get_max_depth() == depth);
        assert(balanced.check_height_balanced());
    }};

    test_helper({1}, 0);
    test_helper({1, 2}, 1);
    test_helper({1, 2, 3}, 1);
    test_helper({1, 2, 3, 4}, 2);
    test_helper({1, 2, 3, 4, 5}, 2);
    test_helper({1, 2, 3, 4, 5, 6}, 2);
    test_helper({1, 2, 3, 4, 5, 6, 7}, 2);
    test_helper({1, 2, 3, 4, 5, 6, 7, 8}, 3);
    test_helper(
        {-5,  -4,  -3,  -2,  7,   8,   9,  10, 11, 120, 121, 122, 123, 124, 125,
         -34, -35, -36, -37, -38, -39, 30, 31, 32, 33,  34,  35,  36,  37},
        4);
    return 0;
}