https://leetcode.com/problems/repeated-substring-pattern/

Easy But tough for me as I do not know two of the algorithms

1. Knuth-Morris-Pratt Algorithm and

2. Divisors + Rabin-Karp

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"
Output: False

Example 3:

Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

Solution:

My intuition: We use the…

Medium — Leetcode: https://leetcode.com/problems/decoded-string-at-index/solution/

An encoded string S is given. To find and write the decoded string to a tape, the encoded string is read one character at a time and the following steps are taken:

• If the character read is a letter, that letter is written onto the tape.
• If the character read is a digit (say d), the entire current tape is repeatedly written d-1 more times in total.

Now for some encoded string S, and an index K, find and return the K-th letter (1 indexed) in the decoded string.

Example 1:

Input: S = "leet2code3", K…

Medium(https://leetcode.com/problems/populating-next-right-pointers-in-each-node/submissions/)

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

• You may only use constant extra space.
• Recursive approach is fine, you may assume implicit stack space does not count as extra space…

Medium : https://leetcode.com/problems/binary-tree-right-side-view/

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Solution

DFS vs. BFS

There are two ways to traverse the tree: DFS depth first search and BFS breadth first search. Here is a small summary

BFS traverses level by level, and DFS first goes to the leaves.

Iterative — Easy : https://leetcode.com/problems/symmetric-tree/

Recursive — Medium [ very important and intuitive]

Hint : 1. A Tree is symmetric to itself. So if you implement a function which accepts two trees to check for symmetry, you can start the first call of the function with symmetric(root, root).

Problem Statement:

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
   / \…

Easy

Sum of Left Leaves

Easy : 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   7There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

Iterative Code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class…

Medium- Hard, https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/solution/

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

During interview:

1. Its good to point out the differences in the space complexity of the BFS (using a queue) and DFS (recursion ) approaches.
2. Both solutions are below.

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Intuition,

1. It is quite evident that we are traversing one level at…

Following the previous post on BF traversal of BSTrees, here is another cool problem often can be easily described using two different data structures. A dictionary and a Tree at play. Please read along ..

Problem

Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, print the top view of it. The output nodes can be printed in any order.

A node x is there in output if x is the topmost node at its horizontal distance. Horizontal distance of left child of a node x…