SWE Interview preparation

https://leetcode.com/problems/house-robber-iii/ The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the police. Example 1: Input: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 Output: 7 Explanation:  Maximum amount of money the thief can rob = 3 + 3 + 1 = 7 . Example 2: Input: [3,4,5,1,3,null,1]   3 / \ 4 5 / \ \ 1 3 1 Output: 9 Explanation:  Maximum amount of money the thief can rob = 4 + 5 = 9 . --- Intuition At each child node, we need to know whether parent was robbed or not If...

https://leetcode.com/problems/sum-of-left-leaves/ Find the sum of all left leaves in a given binary tree. Example: 3 / \ 9 20 / \ 15 7 There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24 . --- Intuition If leaf node, and left leaf - contribute to sum We still need to traverse right child as well, they might have left leaf node Start with root, recurse top down --- Time - O(n) Space - O(h) ---

https://leetcode.com/problems/same-tree/ Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] Output: true Example 2: Input: 1 1 / \ 2 2 [1,2], [1,null,2] Output: false Example 3: Input: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] Output: false --- Intuition Start with root node If both are null - true If one is null other non null - false If value is different - false Recurse into corresponding left, and right nodes --- Time - O(n) Space - O(h)