Comparing Left and Right Branch of a Complete Binary Tree

  • 时间:2020-09-20 14:08:18
  • 分类:网络文摘
  • 阅读:76 次

A complete binary tree is a binary tree that each level except possibiliy the last level, is completed filled. Suppose you are giving a binary tree represented as an array. For example, [3, 6, 2, 9, -1, 10] retpresents the following binary tree, where -1 indicates it is a NULL node.

    3
  6   2
9    10

Write a function that determines whether the left or right branch of the tree is larger. The size of each branch is the sum of the node vlaues. The function should return the string “Right” if the right side is larger and “Left” if the left side is larger. If the tree has zero nodes or if the size of the branches are equal, an empty string “” should be returned.

How to Store/Index a Complete Binary Tree?

We can use an array to index/store a complete binary tree where the root index starts at ONE, and the left child index is always twice its parent index, and the right index is the twice parent index plus one.

For example, in above complete binary tree, the Node 6 has index 2 which is equal to 2*ROOT = 2 * 1. and the Node 2 is 2*ROOT+1 = 2*1+1 = 3.

In the following Javascript method, we have inlined local recursive method that takes the array (complete binary tree) and a node index, which will recursively sum up the nodes in the branch until it gets to the leave nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const solution = (arr) => {
    if (!arr) return "";
    if (arr.length === 0) return "";    
    const sum = (arr, idx) => {
        if (idx - 1 < arr.length) {
            if (arr[idx - 1] === -1) return 0;
            return arr[idx - 1] + sum(arr, idx * 2) + sum(arr, idx * 2 + 1);
        }
        return 0;
    };
    const left = sum(arr, 2);
    const right = sum(arr, 3);
    return (left == right) ? "" : (left > right ? "Left" : "Right");
};
const solution = (arr) => {
    if (!arr) return "";
    if (arr.length === 0) return "";    
    const sum = (arr, idx) => {
        if (idx - 1 < arr.length) {
            if (arr[idx - 1] === -1) return 0;
            return arr[idx - 1] + sum(arr, idx * 2) + sum(arr, idx * 2 + 1);
        }
        return 0;
    };
    const left = sum(arr, 2);
    const right = sum(arr, 3);
    return (left == right) ? "" : (left > right ? "Left" : "Right");
};

Then we can simply call the function twice to compute the sum for left and right branch respectively. The time complexity is O(N) where N is the number of the nodes in the complete binary tree. And the space complexity is O(logN) because the recursion implies a call stack, and the depth for a complete binary tree is O(logN).

binary-tree-left-sum-or-right-sum-larger Comparing Left and Right Branch of a Complete Binary Tree algorithms javascript recursive

binary-tree-left-sum-or-right-sum-larger

You can practice this problem at Hired.com which is a nice career platform for programmers.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
Social Media Cheatsheet of Keyboard Shortcuts 2016 Edition  Tanzania Plagued By Censorship, Offers Journalists A Course On D  Young Cancer Patient Has Decided To Live-Blog His Health’s Decli  How a CDN can be your Blog’s Secret Weapon  Why Wasted Words Kill Good Ideas And Cost Sales  Why You Need Niche Experience to Be a Great Blogger  The Art of the Perfect Listicle  Tools and Resources to Help Create Your Next Content Calendar  5 Tips for Capturing More Leads on Your Blog  Don’t Fall Victim to the Content Overproduction Trap 
评论列表
添加评论