Given the root of a binary tree, return the inorder traversal of its nodes’ values.

The inorder traversal of a binary tree is the nodes in the tree listed in the order they would be visited by an inorder traversal. To solve this problem, we can use a stack to keep track of the nodes we have visited. We will push the root node onto the stack and then pop it off when we are done visiting its left subtree. We will then visit the right subtree of the root.

In this blog post, we will solve leetcode question 94 – Binary Tree Inorder Traversal. This is a classic computer science problem that can be solved using a number of different algorithms. We will discuss two different solutions – a recursive solution and an iterative solution. Let’s get started!

Simplifying the problem

Leetcode 94 question asks us to traverse a binary tree in order. In order to make this easier, let’s simplify the problem by thinking about it as traversing a linked list instead of a binary tree. We can think of each node in the tree as having two pointers – one pointing to the left child and one pointing to the right child.

We are placingall the left nodes of the current node into stack. node is now null since we keep assigning node to its left node after placing the current node into stack.

Solutions

Recursive Solution

The recursive solution for leetcode 94 is a straightforward one. We can use a simple recursive function to traverse the binary tree in order from left to right. We start by visiting the left-most node and then recursively call our function on each of its children (the left and right nodes). This will cause our function to traverse the tree in order from left to right.

Iterative Solution

The iterative solution for leetcode 94 is slightly more complex, but still manageable. We can use a stack to store our current node and its children (the left and right nodes). We start by pushing the root node of the binary tree onto the stack and then while the stack is not empty, we pop a node off of it. We then process it by printing its value and pushing its left and right nodes (if they are not null) onto the stack. Then, when there are no more nodes on the stack, our inorder traversal will be complete.

Solution one is using a stack. Here is the code in JavaScript

var inorderTraversal = function(root) {
    var stack = [];
    var result = [];
    
    // while there is a root or there are still nodes in the stack
    while(root || stack.length){
        // while there is a root
        // push the root into the stack
        // and set the root to the root's left child
        while(root){
            stack.push(root);
            root = root.left;
        }
        // set the root to the node at the top of the stack
        root = stack.pop();
        // push the root's value into the result array
        result.push(root.val);
        // set the root to the root's right child
        root = root.right;
    }
    
    return result;
};

Code in Python

def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result, stack = [], [(root, False)]
        while stack:
            root, is_visited = stack.pop()
            if root is None:
                continue
            if is_visited:
                result.append(root.val)
            else:
                stack.append((root.right, False))
                stack.append((root, True))
                stack.append((root.left, False))
        return result

Code in Java

   public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }
        
        return result;
    }

The time complexity is O(n) and the space complexity is O(n).

From Leetcode:

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

What is being asked?

The questions seems to be pretty straight forward. Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7],

/*
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

*/

return its level order traversal as: [ [3], [9,20], [15,7] ]

What are ways to solve it?

There are multiple ways to solve this problem. One way would be to use a queue. We would start by putting the root node into the queue. Then, we would loop through the queue until it is empty. For each node in the queue, we would add its left and right child nodes (if they exist) to the queue. We would also add the value of the node to our result array.

What is the most optimal Way?

The most optimal way to solve this problem would be to use a breadth-first search algorithm.
The time complexity of this algorithm is O(n), where n is the number of nodes in the tree. The space complexity is also O(n), since we need to store the nodes in the queue as well as the values in the result array. Let’s code this one.

var levelOrder = function(root) {
  // create a queue and result array
  let queue = [root];
  let result = [];
  
  // if the root is null, return an empty array
  if (!root) return result;
  
  // loop through the queue until it is empty
  while (queue.length > 0) {
    // store the size of the queue
    let size = queue.length;
    
    // create an array to store the values for this level
    let level = [];
    
    // loop through the queue
    for (let i = 0; i < size; i++) {
      // dequeue a node
      let node = queue.shift();
      
      // add the value of the node to the level array
      level.push(node.val);
      
      // if the node has a left child, add it to the queue
      if (node.left) queue.push(node.left);
      
      // if the node has a right child, add it to the queue
      if (node.right) queue.push(node.right);
    }
    
    // add the level array to the result array
    result.push(level);
  }
  
  // return the result array
  return result;
};

Question from Leetcode.

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

What are they asking?

Let’s break down the question. Leetcode 31(Next Permutation) is asking for the next permutation of an array of integers. A permutation is an arrangement of the members of an array into a sequence. The next permutation is the next lexicographically greater permutation of the array. This means that if the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such an arrangement is not possible, the array must be rearranged as the lowest possible order (i.e. sorted in ascending order).

Solving the problem

There are a few ways to solve this, we will do so in JavaScript & Java:

There are a few solutions to solving Leetcode 31 Next Permutation. One solution is to find the next largest permutation by reversing the order of the elements from the end of the array. Another solution is to find the next smallest permutation by swapping the first and second elements, then reversing the order of the elements from the end of the array.

The most optimal way would be to find the next largest permutation by reversing the order of the elements from the end of the array.

Here is the code in JavaScript:

function nextPermutation(nums) {
  // Start from the second last element in the array and keep track of the largest element found so far
  var i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }
  // If the largest element is not the first element, then swap it with the next largest element
  if (i >= 0) {
    var j = nums.length - 1;
    while (j >= 0 && nums[j] <= nums[i]) {
      j--;
    }
    swap(nums, i, j);
  }
// Reverse the order of the elements from the end of the array
  reverse(nums, i + 1);
  return nums;
}

function swap(nums, i, j) {
  var temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

function reverse(nums, start) {
  var i = start,
    j = nums.length - 1;
  while (i < j) {
    swap(nums, i, j);
    i++;
    j--;
  }
}

The time complexity is O(n) and the space complexity is O(1).

Here is the code in Java:

public class Solution {
    public void nextPermutation(int[] nums) {
        // Start from the second last element in the array and keep track of the largest element found so far
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // If the largest element is not the first element, then swap it with the next largest element
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }

        // Reverse the order of the elements from the end of the array
        reverse(nums, i + 1);
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

Other Array Problems:

• Maximum Product Subarray
• Solving k largest(or smallest) elements in an array
• Combination Sum

Question: Write an efficient program for printing k largest elements in an array. Elements in an array can be in any order.
For example: if the given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30, and 23.

There are a few different ways to do this. One way would be to keep track of the k largest elements as you iterate through the array, replacing elements in your “k largest” list with larger elements from the array as you encounter them. Another way would be to first sort the array, then print the last k elements.

This is a common Amazon Interview Question.

What is the most efficient way?

The most efficient way would be to keep track of the k largest elements as you iterate through the array, replacing elements in your “k largest” list with larger elements from the array as you encounter them.

Here is one possible implementation in JavaScript:

function printKLargest(arr, k) {
  // create an empty list to track the k largest elements
  var kLargest = [];

  // iterate through the array
  for (var i = 0; i < arr.length; i++) {
    // if the list is not full, simply add the element to the list
    if (kLargest.length < k) {
      kLargest.push(arr[i]);
    }
    // if the list is full, compare the current element to the smallest element in the list
    // if the current element is larger, replace the smallest element with the current element
    else {
      var min = Math.min.apply(null, kLargest);
      if (arr[i] > min) {
        var index = kLargest.indexOf(min);
        kLargest[index] = arr[i];
      }
    }
  }

  // print the k largest elements
  return kLargest;
}
//Driver Code
const args = [30,4,8,8,8];

const ans = printKLargest(args,2)
// Will print [30,8] 2 largest numbers in array
console.log(ans)

Here is the code in Java.

public class printKLargest {
  public static void printKLargest(ArrayList<Integer> arr, int k) {
    // create an empty list to track the k largest elements
    ArrayList<Integer> kLargest = new ArrayList<Integer>();
    // iterate through the array
    for (int i = 0; i < arr.size(); i++) {
      // if the list is not full, simply add the element to the list
      if (kLargest.size() < k) {
        kLargest.add(arr.get(i));
      }
      // if the list is full, compare the current element to the smallest element in the list
      // if the current element is larger, replace the smallest element with the current element
      else {
        int min = Collections.min(kLargest);
        if (arr.get(i) > min) {
          int index = kLargest.indexOf(min);
          kLargest.set(index, arr.get(i));
        }
      }
    }
    // print the k largest elements
    return kLargest;
  }
}

The most efficient way to print the k largest elements in an array is to keep track of the k largest elements as you iterate through the array, replacing elements in your “k largest” list with larger elements from the array as you encounter them.

In this post, we explore a classic coding challenge from Leetcode: problem 39, “Combination Sum.” This problem tests a developer’s ability to find all possible combinations of elements in a given array that add up to a specific target value. We discuss the problem statement in detail, provide an example solution in JavaScript & Java, and discuss some key insights and tips for solving this problem effectively.

From Leetcode:

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

What is the problem asking?

The idea is to use backtracking. We start with an empty list and keep adding elements to it until we reach the target sum. We iterate over all the elements in the array and add them to the list if they don’t exceed the target sum.

We then recursively call the same function with the updated target sum and list. We keep doing this until we either reach the target sum or we run out of elements to add. We then remove the last element from the list and try adding the next element in the array.

We keep doing this until we either reach the target sum or we run out of elements to add. We keep doing this until we either reach the target sum or we run out of elements to add. We then return the list.

One thing to note is that we need to sort the array first in order for this approach to work. This is because, without sorting, there may be cases where we reach the target sum earlier but still have elements left in the array which can lead to duplicate combinations. By sorting the array, we ensure that all possible combinations are explored before moving on to the next element in the array.

Overall, this solution has a time complexity of O(n^m) where n is the length of the candidates array and m is the target sum. This is because at each step, we have n choices and we repeat this process m times until we reach the target sum. The space complexity is O(m) as at each step, we can potentially add a new combination to the output list.

Solving Leetcode 39 in Java:

class Solution {
    public List < List < Integer >> combinationSum(int[] candidates, int target) {
        List < List < Integer >> result = new ArrayList < > ();
        if (candidates == null || candidates.length == 0) {
            return result;
        }

        List < Integer > curr = new ArrayList < > ();
        dfs(candidates, target, 0, curr, result);
        return result;
    }

    private void dfs(int[] candidates, int target, int index, List < Integer > curr, List < List < Integer >> result) {
        if (target == 0) {
            result.add(new ArrayList < > (curr));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            if (target - candidates[i] >= 0) {
                curr.add(candidates[i]);
                dfs(candidates, target - candidates[i], i, curr, result);
                curr.remove(curr.size() - 1);
            }
        }

    }
}

Solution in JavaScript:

const combinationSum = (candidates, target) => {
  const res = [];
  const dfs = (start, sum, path) => {
    if (sum > target) return;
    if (sum === target) {
      res.push(path.slice());
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      dfs(i, sum + candidates[i], path);
      path.pop();
    }
  };
  dfs(0, 0, []);
  return res;
};

LeetCode 39 problem is a great challenge for any coding enthusiast. By using a combination of backtracking and recursion, the problem can be solved efficiently. While this approach may not be the most straightforward solution, it is an effective way to find all possible combinations of integers that add up to the target number. With a bit of practice, it can be a great tool to help you master the basics of coding.

Similar Questions:

• Combinations