NeetCode problems

Hash set or hash set length.

Complexity O(n) time and O(n).

Contains Duplicate - Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.

Array of size 26, increment values for one string, decrement for the other, check if all values are zero in the end. Also do an initial check of string lengths.

Complexity O(n + m) time and O(1), n is the length of the string s and m is the length of the string t.

Valid Anagram - Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

Hash map using single pass. Iterate through the array and record the indices as values and diff = target - nums[i] as key. If diff found, return.

Complexity O(n) time and O(n).

Two Sum - Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.

You may assume that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

Hash map. Iterate the strings, in an array of size 26 count the number of characters, join it to create a key, add string to the hash map under the key, return values of hash map.

Complexity O(m * n) time and O(m) space, m is the number of strings and n is the length of the longest string.

Group Anagrams - Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.

Input: strs = ["act","pots","tops","cat","stop","hat"]

Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]]

Bucket sort. First count with hash map where key is num and value is incremented. Then convert to freq array with length of nums array where key is the value from count and value are the keys, i.e. nums. Finally go through the freq array from back and get numbers until we have k of them.

Complexity O(n) time and O(n).

Top K Frequent Elements - Given an integer array nums and an integer k, return the k most frequent elements within the array.

For the given example the encoded string should look like 4#neet4#code4#love3#you. Start with pointer at 0, read the string until we encounter #, get number before # which tells us by how much we have to move the pointer, get a substring, update pointer.

Complexity O(m) time and O(n), m is the sum of lengths of all strings.

Encode and Decode Strings - Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.

Input: ["neet","code","love","you"]

Encoded string e.g. neet#code#love#you // doesn't work

Output: ["neet","code","love","you"]

Two arrays which store products of all numbers before and after the index. The final array calculates the value by multiplying values at the same index. Can be done in two passes in total optimally.

Complexity O(n) time and O(n).

Products of Array Except Self - Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].

Input: [1,2,4,6]

Output: [48,24,12,8]

Three hash set for rows, columns and squares.

Complexity O(n^2) time and O(n^2) space, n is the number of rows. Can also be solved using bitmask reducing space to O(n).

Valid Sudoku - You are given a 9 x 9 Sudoku board. A Sudoku board is valid if the following rules are followed:

Each row must contain the digits 1-9 without duplicates.

Each column must contain the digits 1-9 without duplicates.

Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.

Return true if the Sudoku board is valid, otherwise return false

Note: A board does not need to be full or be solvable to be valid

Hash set - convert nums to set, iterate and check if a number has a left neighbor. If not, start counting a sequence from there by checking all the right neighbors, keep track of sequence length, update longest sequence variable.

Complexity O(n) time and O(n).

Longest Consecutive Sequence - Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.

Stack - push opening parentheses on stack, pop closing ones and check they match.

Complexity O(n) time and O(n) space.

Valid Parentheses - You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.

Two stacks, one for storing the actual values, another for storing the minimum values.

Minimum Stack - Design a stack class that supports the push, pop, top, and getMin operations.

• MinStack() initializes the stack object.

• void push(int val) pushes the element val onto the stack.

• void pop() removes the element on the top of the stack.

• int top() gets the top element of the stack.

• int getMin() retrieves the minimum element in the stack.

Each function should run in O(1) time.

Stack - push non-operator tokens, in case of operator pop the last two values, run the operation for the two values and push it back on the stack.

Complexity O(n) time and O(n) space.

Evaluate Reverse Polish Notation - You are given an array of strings tokens that represents a valid arithmetic expression in Reverse Polish Notation.

Return the integer that represents the evaluation of the expression.

The operands may be integers or the results of other operations.

The operators include '+', '-', '*', and '/'.

Assume that division between integers always truncates toward zero.

Backtracking - recursion with zero opening, zero closed, empty string, n and the res. Push to res in the base case where opening = closed and opening = n. Go through two branches, if open smaller than n, add opening, if closed smaller than opening, add closed.

Complexity O(4^n/n^(1/2)) time and O(n) space.

Generate Parentheses - You are given an integer n. Return all well-formed parentheses strings that you can generate with n pairs of parentheses.

Stack - have a zero pre-filled res array of temperatures length and a stack of tuples of temperatures and indices. Iterate through temperatures, loop through the stack while current temperature is higher than the last value on the stack in which case pop from the stack and update res value on the popped index to current index minus the popped one. Always push new tuple.

Daily Temperatures - You are given an array of integers temperatures where temperatures[i] represents the daily temperatures on the ith day.

Return an array result where result[i] is the number of days after the ith day before a warmer temperature appears on a future day. If there is no day in the future where a warmer temperature will appear for the ith day, set result[i] to 0 instead.

Stack - pair the two arrays and sort by position. Iterate pairs, push time to distance to that stack, i.e. (target - position) / speed. If time of the top stack is smaller or equal to the second value on stack, pop from the stack. Return length of the stack.

Complexity O(nlogn) time and O(n) space.

Car Fleet - There are n cars traveling to the same destination on a one-lane highway.

You are given two arrays of integers position and speed, both of length n.

• position[i] is the position of the ith car (in miles)

• speed[i] is the speed of the ith car (in miles per hour)

The destination is at position target miles.

A car can not pass another car ahead of it. It can only catch up to another car and then drive at the same speed as the car ahead of it.

A car fleet is a non-empty set of cars driving at the same position and same speed. A single car is also considered a car fleet.

If a car catches up to a car fleet the moment the fleet reaches the destination, then the car is considered to be part of the fleet.

Return the number of different car fleets that will arrive at the destination.

Stack - Keep a stack of pairs of indices and heights. While top of the stack’s height is larger than the current height, pop values, update the index to store to the popped one and update largest area using the popped values. After the loop, go through the remainder of the stack updating the largest area.

Complexity O(n) time and O(n) space.

Largest Rectangle In Histogram - You are given an array of integers heights where heights[i] represents the height of a bar. The width of each bar is 1.

Return the area of the largest rectangle that can be formed among the bars.

Two pointers - Left at start, right at the end, skip non-alpha numeric characters.

Complexity O(n) time and O(1) space.

Valid Palindrome - Given a string s, return true if it is a palindrome, otherwise return false.

A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.

Two pointers - Left at start, right at the end, loop while sum is not target, if sum bigger than target, decrement right, else increment left. Return integers incremented by one.

Complexity O(n) time and O(1) space.

Two Integer Sum II - Given an array of integers numbers that is sorted in non-decreasing order.

Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.

There will always be exactly one valid solution.

Your solution must use O(1) additional space.

Two pointers - This adopts 2Sum solution. As the time complexity will be O(n²), we can sort “for free”. We will use all the negative numbers as the target for 2Sum. Two checks for duplicates. One, skip duplicate target negative numbers, two, after pushing correct triplet where the search will continue, increment the left pointer until it’s different from the previous value.

Complexity O(n²) time and O(1) space.

3Sum - Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.

The output should not contain any duplicate triplets. You may return the output and the triplets in any order.

Two pointers - Left at 0, right at end of heights array. Each iteration update most water (multiply length r-l by min of the current heights). Increment pointer which is currently the smallest height.

Complexity O(n) time and O(1) space.

Container With Most Water - You are given an integer array heights where heights[i] represents the height of the ith bar.

You may choose any two bars to form a container. Return the maximum amount of water a container can store.

Two pointers - Left at 0, right at end. Also keep track of maximum left and right heights. In the iteration, if left maximum is smaller than right maximum, increment left integer, update left maximum and accumulator. Vice versa for the other case.

Complexity O(n) time and O(1) space.

Trapping Rain Water - You are given an array non-negative integers height which represent an elevation map. Each value height[i] represents the height of a bar, which has a width of 1.

Return the maximum area of water that can be trapped between the bars.

Binary search. While l <= r, calculate midpoint and update l and r accordingly if not target, otherwise return target and -1 outside of while.

Complexity O(logn) time and O(1) space.

Binary Search - You are given an array of distinct integers nums, sorted in ascending order, and an integer target.

Implement a function to search for target within nums. If it exists, then return its index, otherwise, return -1.

Binary search. The only complication here is translation the calculated midpoint to matrix rows and columns.

Complexity O(log(m * n)) time and O(1) space.

Search a 2D Matrix - You are given an m x n 2-D integer array matrix and an integer target.

Each row in matrix is sorted in non-decreasing order.

The first integer of every row is greater than the last integer of the previous row.

Return true if target exists within matrix or false otherwise.

Binary search. Left = 0, right = max value from the piles. Track result. While l <= r, calculate midpoint k, based on this calculate the number of hours needed to eat all piles, if hours needed bigger than h, update l = k + 1, else update res and r = k - 1, return res.

Complexity O(nlogm) time and O(1) space, where n is the size of the input array, and m is the maximum value in the array.

Koko Eating Bananas - You are given an integer array piles where piles[i] is the number of bananas in the ith pile. You are also given an integer h, which represents the number of hours you have to eat all the bananas.

You may decide your bananas-per-hour eating rate of k. Each hour, you may choose a pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, you may finish eating the pile but you can not eat from another pile in the same hour.

Return the minimum integer k such that you can eat all the bananas within h hours.

Binary search. Start with l at start, r at end, while l < r calculate mid point, if mid point number smaller then right number, move r, else move l to m+1 (since that one is nums[m] >= nums[l]). Return nums[l].

Complexity O(logn) time and O(1) space.

Find Minimum in Rotated Sorted Array - You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become [3,4,5,6,1,2] if it was rotated 4 times.

Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array.

Binary search. Start with l at start, e at end, while l < r calculate mid point. If target equals mid point number, return it. If num at midpoint is larger or equal to left number, we are in the left section. In that case, if target is larger that number at midpoint or target is smaller than number at left pointer, move left pointer, otherwise move right. Similar case applies if nums[l] > nums[m]. Return -1 at the end.

Complexity O(logn) time and O(1) space.

Search in Rotated Sorted Array - You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become [3,4,5,6,1,2] if it was rotated 4 times.

Given the rotated sorted array nums and an integer target, return the index of target within nums, or -1 if it is not present.

You may assume all elements in the sorted rotated array nums are unique.

Binary search in hash set. Store array of tuples (value and timestamp) in hash set. Binary search on the array, init res to empty string, update res only when updating left pointer, return res.

Complexity O(1) time for set(), O(logn) time for get(), and O(m * n) space, where n is the total number of values associated with a key, and m is the total number of keys.

Time Based Key-Value Store - Implement a time-based key-value data structure that supports:

• Storing multiple values for the same key at specified time stamps

• Retrieving the key's value at a specified timestamp

Implement the TimeMap class:

• TimeMap() Initializes the object.

• void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.

• String get(String key, int timestamp) Returns the most recent value of key if set was previously called on it and the most recent timestamp for that key prev_timestamp is less than or equal to the given timestamp (prev_timestamp <= timestamp). If there are no values, it returns "".

Note: For all calls to set, the timestamps are in strictly increasing order.z

Binary search. First, ensure first array is shorter or equal to second array. Init l to 0, r to length of first array. Calculate mid point - this is a cut off point for the first array. From this, calculate length of the second array. We found the correct cut off point if the element to the left of the mid point of first array (Aleft) is smaller or equal to the element to the right of the mid point of the second array (Bright) and element to the left of the mid point of second array (Bleft) is smaller or equal to the element to the right of the mid point of the first array (Aright). Edge cases at the ends of the arrays has to be handled with positive and negative infinity. If the total length is even, calculate median as average of max of Aleft and Bleft and min of Aright and Bright. If odd, take max of the elements Aleft and Bleft (since we take round up half length of the array). If Aleft is larger than Bright, update right pointer, else update left.

Complexity O(log(min(n, m))) time and O(1) space.

Median of Two Sorted Arrays - You are given two integer arrays nums1 and nums2 of size m and n respectively, where each is sorted in ascending order. Return the median value among all elements of the two arrays.

Update pointers. Start with prev being null and curr pointing to head. Iterate until curr present, store curr’s next to temp var, update curr’s next to prev, prev to curr and curr to temp. Return prev.

Complexity O(n) time and O(1) space.

Reverse Linked List - Given the beginning of a singly linked list head, reverse the list, and return the new beginning of the list.

Use dummy node and iterate until both list1 and list2 are present. Check which value is bigger, update merged list’s next accordingly and advance lists. At the end, attach remainder of list1 or list2 to the end, return dummy’s next.

Complexity O(n + m) time and O(1) space. Where n is the length of list1 and m is the length of list2.

Merge Two Sorted Linked Lists - You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted linked list and return the head of the new sorted linked list.

The new list should be made up of nodes from list1 and list2.

Floyd’s hare and tortoise - fast and slow pointers, iterate until fast or fast’s next is null, advance pointers accordingly, check if slow equals fast, in which case we’ve detected a cycle.

Complexity O(n) time and O(1) space.

Linked List Cycle Detection - Given the beginning of a linked list head, return true if there is a cycle in the linked list. Otherwise, return false.

There is a cycle in a linked list if at least one node in the list can be visited again by following the next pointer.

Internally, index determines the index of the beginning of the cycle, if it exists. The tail node of the list will set it's next pointer to the index-th node. If index = -1, then the tail node points to null and no cycle exists.

Note: index is not given to you as a parameter.

Two passes - using slow and fast pointers, find middle of the list. Reverse second half. Then start with curr at head and prev at end and update pointers accordingly. Two temp variables for curr and prev nexts will be needed. Point curr’s next to prev, prev’s next to curr’s temp, update prev and curr to their temps. Return head.

Complexity O(n) time and O(1) space.

Reorder Linked List - You are given the head of a singly linked-list.

The positions of a linked list of length = 7 for example, can intially be represented as:

[0, 1, 2, 3, 4, 5, 6]

Reorder the nodes of the linked list to be in the following order:

[0, 6, 1, 5, 2, 4, 3]

Notice that in the general case for a list of length = n the nodes are reordered to be in the following order:

[0, n-1, 1, n-2, 2, n-3, ...]

You may not modify the values in the list's nodes, but instead you must reorder the nodes themselves.

Two pointers. Advance right pointer by n. Due to one-off error, start left at dummy. Advance both pointer until right is null. Left is then before the node to be removed so point left's next to left'‘s next’s next.

Complexity O(N) time and O(1) space, where N is the length of the given list.

Remove Node From End of Linked List - You are given the beginning of a linked list head, and an integer n.

Remove the nth node from the end of the list and return the beginning of the list.

Two passes and hash map. Add null to map. In first pass, create new nodes, use existing nodes as keys. In second pass, get the new node, set next and random nodes from the current node, return head from map.

Complexity O(n) time and O(n) space. It’s possible to do it in O(1) space.

Copy Linked List with Random Pointer - You are given the head of a linked list of length n. Unlike a singly linked list, each node contains an additional pointer random, which may point to any node in the list, or null.

Create a deep copy of the list. Return the head of the copied linked list.

Init new list node l3, keep track of current node and carry. While either l1, l2 or carry is still available, iterate. Calculate the sum, default empty list values to 0. Create next node with sum % 10. Update carry to sum / 10. Advance all lists. Return l3’s next.

Complexity O(m+n) time and O(1) space where m is length of l1 and n is length of l2.

Add Two Numbers - You are given two non-empty linked lists, l1 and l2, where each represents a non-negative integer.

The digits are stored in reverse order, e.g. the number 123 is represented as 3 -> 2 -> 1 -> in the linked list.

Each of the nodes contains a single digit. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Return the sum of the two numbers as a linked list.

Linked list cycle problem, solve using Floyd’s algo. Two pointers, slow and fast. Advance pointers using list values as indices until slow and fast overlap. At this point, start another slow pointer at head and advance both slow pointers until they meet and return that value.

Proof for why Floyd’s algo works: p is distance before cycle start from head, x is distance before cycle start within cycle, c is cycle length. 2*slow = fast. 2 * (p + c - x) = p + c - x + c which simplifies to p = x.

Complexity O(n) time and O(1) space.

Find the Duplicate Number - You are given an array of integers nums containing n + 1 integers. Each integer in nums is in the range [1, n] inclusive.

Every integer appears exactly once, except for one integer which appears two or more times. Return the integer that appears more than once.

We’ll need doubly linked list, nodes store both value and key. Class has capacity, hash map, left and right pointers init to dummy nodes pointing to each other. Two util methods for removing node and inserting node at right. Get returns -1 if key not found, otherwise it removes and inserts the node and return it’s value. Put removes the node if it already exists, sets the value in hash map and inserts the node. If size of hash map bigger than capacity, LRU is left’s next, remove LRU and delete it from hash map.

Complexity O(1) time and O(n) space.

LRU Cache - Implement the Least Recently Used (LRU) cache class LRUCache. The class should support the following operations

• LRUCache(int capacity) Initialize the LRU cache of size capacity.

• int get(int key) Return the value corresponding to the key if the key exists, otherwise return -1.

• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the introduction of the new pair causes the cache to exceed its capacity, remove the least recently used key.

A key is considered used if a get or a put operation is called on it.

Use merge two sorted linked lists solution in a merge sort fashion. While there are more than one list to sort, take pairs of lists and merge them.

Complexity O(nlogk) time and O(k) space where k is the total number of lists and n is the total number of nodes across k lists.

Merge K Sorted Linked Lists - You are given an array of k linked lists lists, where each list is sorted in ascending order.

Return the sorted linked list that is the result of merging all of the individual linked lists.

Start at dummy, maintain prev group pointer starting at dummy. Get kth node (break if null) and maintain next group pointer at kth’s next. Reverse nodes, starting with prev being kth’s next and curr being previous group’s next, until curr isn’t next group pointer. We then need to update previous group itself and it’s next pointer. Return dummy’s next.

Complexity O(n) time and O(1) space.

Reverse Nodes in K-Group - You are given the head of a singly linked list head and a positive integer k.

You must reverse the first k nodes in the linked list, and then reverse the next k nodes, and so on. If there are fewer than k nodes left, leave the nodes as they are.

Return the modified list after reversing the nodes in each group of k.

You are only allowed to modify the nodes' next pointers, not the values of the nodes.

Two pointers - Iterate until r reaches prices bounds. If left’s price is larger than right’s price, set left to right, otherwise update max using max of current max and price diff. Advance right pointer. Return max.

Complexity O(n) time and O(1) space.

Best Time to Buy and Sell Stock - You are given an integer array prices where prices[i] is the price of NeetCoin on the ith day.

You may choose a single day to buy one NeetCoin and choose a different day in the future to sell it.

Return the maximum profit you can achieve. You may choose to not make any transactions, in which case the profit would be 0.

Sliding window - Maintain set of letters, max and two pointers. Iterate until right reaches s’ bounds. Until set contains right’s letters, remove left’s letters from the set advancing left. Add right’s letter to the set, advance right and update max. Return max.

Complexity O(n) time and O(m) space where n is the length of the string and m is the total number of unique characters in the string.

Longest Substring Without Repeating Characters - Given a string s, find the length of the longest substring without duplicate characters.

Sliding window - have a set for character counts, max frequency (maxf) variable, result, left and right pointer. Iterate right pointer until s’ bounds. Update/set count and maxf. While the size of window minus the maxf is larger than k, decrement the count in set and increment the left pointer. Update res. Return res.

Complexity O(n) time and O(m) space where n is the length of the string and m is the total number of unique characters in the string.

Longest Repeating Character Replacement - You are given a string s consisting of only uppercase english characters and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English character.

After performing at most k replacements, return the length of the longest substring which contains only one distinct character.

Sliding window - Check for edge where s1 is longer than s2, return false in that case. Initialize two arrays of length 26 with 0s. Iterate s1, increment values in both arrays where a is 0th index, z is 25th index. Calculate the initial number of matches. Iterate the rest of s2 using l and r pointers. Return true if we have 26 matches. Increment arr2 counts, increment or decrement matches accordingly (strict equals) for right pointer, do the same for left pointer, but decrement arr2 counts.

Complexity O(n) time and O(1) space.

Permutation in String - You are given two strings s1 and s2.

Return true if s2 contains a permutation of s1, or false otherwise. That means if a permutation of s1 exists as a substring of s2, then return true. Both strings only contain lowercase letters.

Sliding window - Two maps for counting chars in the two strings. Iterate t and increment chars in tMap. We’ll compare how many matches we have vs. how many we need. We need as many matches as there are records in tMap. Keep track of res, tuple of left to right indices, start with infinite range. Two pointers, iterate right pointer until s’ bounds. Update counts in sMap, if a record for current letter exists in tMap, compare it with sMap and if it’s strictly equal, increment matches we have. While the matches we have equal matches we need, update res if it’s smaller, decrement sMap value for left pointer, decrement haves if the record for left’s pointer is present and it’s bigger than in sMap increment left pointer. Return substring based on the res, if infinite range, return empty string.

Complexity O(n) time and O(m) space where n is the length of the string s and m is the total number of unique characters in the strings t and s.

Minimum Window Substring - Given two strings s and t, return the shortest substring of s such that every character in t, including duplicates, is present in the substring. If such a substring does not exist, return an empty string "".

You may assume that the correct output is always unique.

Deque - have res array, deque (we’ll store indices), left and right pointer. Iterate until right reaches nums’ bounds. Pop from back until current number is bigger that the number at the end of deque. Push right to deque. If left is bigger than deque front, pop front from deque to stay within window. Add to res the front’s deque num and increment left only after r - 1 iterations. Advance right. Return res.

Complexity O(n) time and O(n) size.

Sliding Window Maximum - You are given an array of integers nums and an integer k. There is a sliding window of size k that starts at the left edge of the array. The window slides one position to the right until it reaches the right edge of the array.

Return a list that contains the maximum element in the window at each step.

Recursive DFS is simplest. Iterative DFS and BFS are also possible. Base case, return null if node is null. Swap node’s left and node’s right. Call recursively on node’s left and node’s right. Return root.

Complexity O(n) time and O(n) size for recursion stack.

Invert Binary Tree - You are given the root of a binary tree root. Invert the binary tree and return its root.

Recursive DFS is simplest. Iterative DFS and BFS are also possible. Base case, return 0 if node is null. Otherwise return 1 + max of recursive call on node’s left and node’s right.

Complexity O(n) time and O(h) size where n is the number of nodes in the tree and h is the height of the tree.

Maximum Depth of Binary Tree - Given the root of a binary tree, return its depth.

The depth of a binary tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

Recursive DFS is simplest. Iterative DFS is also possible. Helper dfs function, base case is to return 0 if node is null. Calculate left and right recursively, update max if left + right is bigger, return 1 + max of left and right.

Complexity O(n) time and O(h) size where n is the number of nodes in the tree and h is the height of the tree.

Diameter of Binary Tree - The diameter of a binary tree is defined as the length of the longest path between any two nodes within the tree. The path does not necessarily have to pass through the root.

The length of a path between two nodes in a binary tree is the number of edges between the nodes.

Given the root of a binary tree root, return the diameter of the tree.

Recursive DFS is simplest. Iterative DFS is also possible. Helper dfs function, pass around node and balanced boolean (as reference). Base case is if no node or not balanced, return 0. Store left and right by calling recursively, if balanced, update balance by checking if absolute difference between left and right is smaller or equal to 1, return 1 + max of left and right.

Complexity O(n) time and O(h) size where n is the number of nodes in the tree and h is the height of the tree.

Balanced Binary Tree - Given a binary tree, return true if it is height-balanced and false otherwise.

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.

Recursive DFS is simplest. Iterative DFS and BFS are also possible. Base case, if not p and not q, return true. If p and q and their values are same, return a logical and of recursive call on p and q’s left and right. Else, return false.

Complexity O(n) time and O(h) size where n is the number of nodes in the tree and h is the height of the tree.

Same Binary Tree - Given the roots of two binary trees p and q, return true if the trees are equivalent, otherwise return false.

Two binary trees are considered equivalent if they share the exact same structure and the nodes have the same values.

…

Complexity O(m+n) time and O(m+n) space where m is the number of nodes in subRoot and n is the number of nodes in root.

Subtree of Another Tree - Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

…

Complexity O(h) time and O(1) space.

Lowest Common Ancestor in Binary Search Tree - Given a binary search tree (BST) where all node values are unique, and two nodes from the tree p and q, return the lowest common ancestor (LCA) of the two nodes.

The lowest common ancestor between two nodes p and q is the lowest node in a tree T such that both p and q as descendants. The ancestor is allowed to be a descendant of itself.

…

Complexity O(n) time and O(n) space.

Binary Tree Level Order Traversal - Given a binary tree root, return the level order traversal of it as a nested list, where each sublist contains the values of nodes at a particular level in the tree, from left to right.

…

Complexity O(n) time and O(n) space.

Binary Tree Right Side View - You are given the root of a binary tree. Return only the values of the nodes that are visible from the right side of the tree, ordered from top to bottom.

…

Complexity O(n) time and O(n) space.

Count Good Nodes in Binary Tree - Within a binary tree, a node x is considered good if the path from the root of the tree to the node x contains no nodes with a value greater than the value of node x

Given the root of a binary tree root, return the number of good nodes within the tree.

…

Complexity O(n) time and O(n) space.

Valid Binary Search Tree - Given the root of a binary tree, return true if it is a valid binary search tree, otherwise return false.

A valid binary search tree satisfies the following constraints:

• The left subtree of every node contains only nodes with keys less than the node's key.

• The right subtree of every node contains only nodes with keys greater than the node's key.

• Both the left and right subtrees are also binary search trees.

…

Complexity O(n) time and O(n) space or O(1) optimally.

Kth Smallest Integer in BST - Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) in the tree.

A binary search tree satisfies the following constraints:

• The left subtree of every node contains only nodes with keys less than the node's key.

• The right subtree of every node contains only nodes with keys greater than the node's key.

• Both the left and right subtrees are also binary search trees.

…

Complexity O(n) time and O(n) space.

Construct Binary Tree from Preorder and Inorder Traversal - You are given two integer arrays preorder and inorder.

• preorder is the preorder traversal of a binary tree

• inorder is the inorder traversal of the same tree

Both arrays are of the same size and consist of unique values.

Rebuild the binary tree from the preorder and inorder traversals and return its root.

…

Complexity O(n) time and O(n) space.

Binary Tree Maximum Path Sum - Given the root of a non-empty binary tree, return the maximum path sum of any non-empty path.

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can not appear in the sequence more than once. The path does not necessarily need to include the root.

The path sum of a path is the sum of the node's values in the path.

…

Complexity O(n) time and O(n) space.

Serialize and Deserialize Binary Tree - Implement an algorithm to serialize and deserialize a binary tree.

Serialization is the process of converting an in-memory structure into a sequence of bits so that it can be stored or sent across a network to be reconstructed later in another computer environment.

You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. There is no additional restriction on how your serialization/deserialization algorithm should work.