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
You can practice this problem at Hired.com which is a nice career platform for programmers.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Find Words That Can Be Formed by Characters?
Next Post: How to Count the Distinct Pairs using HashMap?
Nice solution. Recursion usually scares the pants of me but this is a nice example. I see how you are using the size of the array to limit the level of recursion. I would personally separate out the sum function. I also wonder if it might be better to pass index -1 to the sum function rather that repeating which could make it a little easier to read. But then I see if you changed this you would have to add 1 to transform back from a binary Tree index as opposed to an Array Index.
Thank you. Yes, recursion is like a double-edged sword.
This doesn’t seem to work for a longer array input…the test inputs on hired only go up to an input array length of 6. (Also, entering your own test input doesn’t work on the site atm, I’m talking with support right now about it. So the only way to test is to bring the function into your own environment and run some inputs through it.)
If I understand how the function is supposed to work correctly, given an input array
[3, 6, 2, 9, -1, 10, 11, 4, 7, 8, 1, 5, 0, 0, 0]
[C,L, R, L, L, R, R, L, L, L, L, R, R, R, R]
Left = 6 + 9 + -1(0) + 4 + 7 + 8 + 1 = 35
Right = 2 + 10 + 11 + 5 + 0 + 0 + 0 = 28
Given that input, the output should be “Left”, but with your solution the output is “Right”.
I did come up with one solution that worked…but I submitted it and lost it 🙁 so I’ll have to do it again. But it was ugly, I’m pretty sure there’s a better way to do it.
Here’s my solution that works for any length input array. Like I said, ugly, but works. care to try for a refactor?
const solution = (arr) => {
if (arr.length < 1) return "";
let leftSum = 0;
let rightSum = 0;
for (let leftStartIdx = 1, rightStartIdx = 2; leftStartIdx < arr.length && rightStartIdx < arr.length; leftStartIdx = leftStartIdx + leftStartIdx + 1, rightStartIdx = rightStartIdx + rightStartIdx + 1) {
for (let leftIdx = leftStartIdx; leftIdx < rightStartIdx; leftIdx++) {
if (arr[leftIdx] !== -1) leftSum += arr[leftIdx];
}
let nextLeftIdx = leftStartIdx + leftStartIdx + 1;
for (let rightIdx = rightStartIdx; rightIdx < nextLeftIdx && rightIdx rightSum) {
return “Left”;
} else if (leftSum < rightSum) {
return "Right";
} else {
return "";
}
};
Those & deals are 2 ampersands. recommend copying and pasting into an ide to be able to read…
Thank you very much.
hey Trevor!
I’ve drawn out the tree you describe with the array [3, 6, 2, 9, -1, 10, 11, 4, 7, 8, 1, 5, 0, 0, 0] but it isn’t possible! Nonexistant nodes, represented with a -1, cannot have child nodes. Your array assigns values (7 and 8) to a nonexistant node (-1).
I assume from the example given on Hired that all nonexistant nodes, including their child nodes, are to be represented by a -1.
correction: I meant to say the values it assigns to the null node are 8 & 1***
I’ll add that the algorithm in the original post accounts for this by stopping the subtree calculation when it hits a null node (-1). By excluding the 8 & 1, the left count is 26, making the right branch greater with a count of 28.