## Cousins in Binary Tree

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1. Two nodes of a binary tree are cousins if they have the same depth, but have different parents. We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree. Return true if and only if the nodes corresponding to the values x and y are cousins.

by lek tin in "algorithm" access_time 2-min read

## Check if a String Is a Valid Sequence From Root to Leaves Path in a Binary Tree

Given a binary tree where each path going from the root to any leaf form a valid sequence, check if a given string is a valid sequence in such binary tree. We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree. Example 1: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1] Output: true Explanation: The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure).

by lek tin in "algorithm" access_time 2-min read

## Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place. For example, given the following tree: 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6 Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.

by lek tin in "algorithm" access_time 1-min read

## Delete Nodes and Return Forest

Given the root of a binary tree, each node in the tree has a distinct value. After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees). Return the roots of the trees in the remaining forest. You may return the result in any order. Example 1 Input: root = [1,2,3,4,5,6,7], to_delete = [3,5] Output: [[1,2,null,4],,] Constraints 1 The number of nodes in the given tree is at most 1000.

by lek tin in "algorithm" access_time 1-min read

## Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of every node differ in height by no more than 1. Example 1 Given the following tree [3,9,20,null,null,15,7]: 3 / \ 9 20 / \ 15 7 Return true. Example 2 Given the following tree [1,2,2,3,3,null,null,4,4]: 1 / \ 2 2 / \ 3 3 / \ 4 4 Return false.

by lek tin in "algorithm" access_time 2-min read

## Print Binary Tree

Print a binary tree in an m*n 2D string array following these rules: The row number m should be equal to the height of the given binary tree. The column number n should always be an odd number. The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part).

by lek tin in "algorithm" access_time 2-min read

## Construct Binary Tree From Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree. Note You may assume that duplicates do not exist in the tree. For example, given: preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree: 3 / \ 9 20 / \ 15 7 Hint Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return helper(0, 0, inorder.

by lek tin in "algorithm" access_time 2-min read

## Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow-up the Recursive solution is trivial, could you do it iteratively? Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ """Check root == None to reduce time on checking""" if root == None: return [] stack = [] result = [] current = root while (current!

by lek tin in "algorithm" access_time 1-min read

## Subtree With Maximum Average

Given a binary tree, find the subtree with maximum average. Return the root of the subtree. It’s guaranteed that there is only one subtree with maximum average. Example Given a binary tree: 1 / \ -5 11 / \ / \ 1 2 4 -2 return the node 11. Solution public class Solution { private class ResultType { public int sum, size; public ResultType(int sum, int size) { this.sum = sum; this.

by lek tin in "algorithm" access_time 2-min read

## Validate Subtree

Given two trees, T1 and T2, write an function to test whether T2 is a subtree of T1. Solution public class Subtree { public boolean isSubTree(TreeNode T1, TreeNode T2) { if (T2 == null) return true; if (T1 == null) return false; return (isSameTree(T1,T2) || isSubTree(T1.left, T2) || isSubTree(T1.right, T2)); } public boolean isSameTree(TreeNode T1, TreeNode T2) { if (T1 == null && T2 == null) return true; if (T1 == null || T2 == null) return false; if (T1.

by lek tin in "algorithm" access_time 1-min read