Good afternoon! Here's our prompt for today.
Question
Can you count all the univalued subtrees in a binary tree, as shown in the figure below?
The Problem
We are given a binary tree. The challenge is to count all the univalued subtrees in the tree. Just to recall, a subtree is any node along with its descendants. The root and all its descendants form the entire tree. A univalued subtree is therefore a subtree in which all the nodes have the same keys. The figure below shows all the univalued subtrees of the binary tree of the previous figure.
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx37
var assert = require('assert');function countUniValueSubtrees(root) { let count = 0; if (!root) { return 0; } isUniValHelper(root, count); return count;}function isUniValHelper(node, count) { // Base case: if both children are null, we know the node is a univalue, we can increment count and return true if (node.left === null && node.right === null) { count++; return true; } // Check isUniVal for each child search tree let isUniVal = true; if (node.left !== null) { isUniVal = isUniValHelper(node.left) && isUniVal && node.left.val === node.val; } if (node.right !== null) { isUniVal = isUniValHelper(node.right) && isUniVal && node.right.val === node.val; } // Check if the isUniVal is false. This way, we don't run the next line of code where we add the count if (!isUniVal) return false; // If it's true, we want to increment the count, then return true to inform the other nodes count++; return true;}OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Here's how we would solve this problem...
How do I use this guide?
Access all course materials today
The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.
