Basic binary tree problems

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void helper(vector<vector<int>> &ret, TreeNode* node, int level){
if (node==nullptr)return;
if (ret.size() >=level+1)ret[level].push_back(node->val);
else ret.push_back({node->val});
helper(ret, node->left, level+1);
helper(ret, node->right, level+1);

}
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> ret;
helper(ret, root, 0);
reverse(ret.begin(), ret.end());
return ret;
}
};

100. Same Tree

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if ((p && !q) ||(!p&&q))return false;
else if(p && q)
{
if (p->val != q->val)return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
else return true;
}
};

236. Lowest Common Ancestor of a Binary Tree

C++

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root ==p || root ==q) return root;
if (!root)return nullptr;
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if (left && right)return root;
return left? left: right;

}
};

Python

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root in (None, p, q): return root
left, right = (self.lowestCommonAncestor(kid, p, q)
for kid in (root.left, root.right))
return root if left and right else left or right

106. Construct Binary Tree from Inorder and Postorder Traversal

Non in place got TLE

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size()==0)return nullptr;

auto root_val = postorder.back();postorder.pop_back();
TreeNode* node = new TreeNode(root_val);
vector<int> left_inorder, right_inorder;
set<int> left;
bool is_left = true;
for (auto x : inorder)
{
if (x == root_val)
{
is_left = false;
continue;
}
if (is_left)
{
left_inorder.push_back(x);
left.insert(x);
}
else
{
right_inorder.push_back(x);
}
}
vector<int> left_postorder(postorder.begin(), postorder.begin()+left_inorder.size());
vector<int> right_postorder(postorder.begin()+left_inorder.size() , postorder.end());
TreeNode* left_tree = buildTree(left_inorder, left_postorder);
TreeNode* right_tree = buildTree(right_inorder, right_postorder);
node->left = left_tree;
node->right = right_tree;
return node;
}
};

Inplace got AC

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* helper(map<int, int>& pos, vector<int>& inorder, vector<int>& postorder, int i, int j, int ii, int jj)
{
TreeNode* node = new TreeNode(postorder[jj]);
if (i == j) return node;
auto idx = pos[postorder[jj]];
if (idx == i )
{
node->left = nullptr;
ii = ii + (idx - i);
auto right = helper(pos, inorder, postorder, i+1, j, ii ,jj-1);
node -> right = right;
}
else if (idx == j)
{
jj = ii + (idx - i - 1);
auto left = helper(pos, inorder, postorder, i, j-1, ii , jj);
node->left = left;
node->right = nullptr;
}
else
{
auto new_jj = ii + (idx - i - 1);
auto left = helper(pos, inorder, postorder, i, idx-1, ii , new_jj);
node->left = left;
auto new_ii = ii + (idx - i);
auto right = helper(pos, inorder, postorder, idx+1, j, new_ii ,jj-1);
node -> right = right;
}
return node;

}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
map<int, int> pos;
const int n = inorder.size();
if (n == 0)return nullptr;
for (int i = 0; i < n; ++i)
{
pos[inorder[i]] = i;
}
return helper(pos, inorder, postorder, 0, n-1, 0, n-1);

}
};

987. Vertical Order Traversal of a Binary Tree

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;
class Solution {
public:
void helper(viii& ret, TreeNode* node, int hlevel, int vlevel)
{
if (!node) return;
ret.emplace_back(vlevel, hlevel, node->val);
helper(ret, node->left, hlevel+1, vlevel - 1);
helper(ret, node->right, hlevel+1, vlevel + 1);
}
vector<vector<int>> verticalTraversal(TreeNode* root) {
viii ret;
helper(ret, root, 0, 0);
sort(ret.begin(), ret.end());
// push back a dummy element at the end to make sure that we can contain all the results during the for loops
ret.emplace_back(10000, 10000, 10000);
vector<vector<int>> fin_ret;
int current_level = get<0>(ret.front());
vector<int> this_ret;
for (auto& [vlevel, hlevel, val] : ret)
{
if (vlevel == current_level) this_ret.push_back(val);
else
{
fin_ret.push_back(this_ret);
this_ret.clear();
current_level = vlevel;
this_ret.push_back(val);
}
}
return fin_ret;
}
};

270. Closest Binary Search Tree Value

O(n) solution

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void helper(TreeNode* node, double& target, double& delta, int& ret)
{
if (!node)return;
if (abs(node->val - target) < delta)
{
delta = abs(node->val - target);
ret = node->val;
}
helper(node->left, target, delta, ret);
helper(node->right, target, delta, ret);
}
int closestValue(TreeNode* root, double target) {
double delta = 1e18;
int ret = 0;
helper(root, target, delta, ret);
return ret;
}
};

O(log h) solution

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int closestValue(TreeNode* root, double target) {
int a = root->val;
auto kid = target < a ? root->left : root->right;
if (!kid) return a;
int b = closestValue(kid, target);
return abs(a - target) < abs(b - target) ? a : b;
}
};

437. Path Sum III

For this problem, we need know the parent node of current node. We can simply use the

1

2 3

methods to encode the node index. However, it will get overflow if we only have nodes in one side. In order to solve this problem, we can build a map to recording the parent and child relationships.

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void helper(TreeNode* node, int& i, int& sum, int& ret, vector<unordered_map<int, int>>& m, unordered_map<int, int>& p)
{
if (!node)return;
int parent = p[i];

if (i == 1)
{
m[i][node->val] += 1;
}

else
{
for (auto x: m[parent])
{
m[i][x.first + node->val] += x.second;
}
m[i][node->val] += 1;
}

if (m[i].count(sum))
{
ret+=m[i][sum];
}
int old_i = i;
p[i+1] = old_i;
i++;
helper(node->left, i , sum, ret, m, p);
i++;
p[i] = old_i;
helper(node->right, i , sum, ret, m, p);
}
int pathSum(TreeNode* root, int sum) {
int ret = 0;
vector<unordered_map<int, int>> m(2000);
unordered_map<int, int> p;
p[1] = 0;
int i = 1;
helper(root, i, sum, ret, m, p);
return ret;
}
};

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Manage AWS via CLI

Out-of-Box vs. Custom Software Solutions

LIFE LESSONS | RACE

Github

Publish-Subscribe ( Logic Apps)

Django Tutorial #1: Setup the Project

Architecting a (DNVB) Digital Native Vertical Brand in Consumer Industry — Part 2

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Search in Rotated Sorted Array — Leetcode Python

Data Structure: Arrays and Lists (I)

Box Stack Problem — Recursive way

Stack Data Structure and the Call Stack