Traversal

Create linked lists of all the nodes at each depth for a Binary Tree

Problem Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists) Examples Example 1: Input: 1 / \ 2 3 / \ / \ 4 5 6 7 Output: (1) => NULL (2) => (3) => NULL (4) => (5) => (6) => (7) => NULL ...

Maximum Depth of Binary Tree

Maximum Depth of Binary Tree Problem Given a binary tree, find its maximum depth. Definition A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. The number of nodes along the longest path from the root node down to the farthest leaf node. Depth of root node is 0. Example Example 1 ...

Binary Tree Preorder Traversal

Problem Given the root of a binary tree, return the preorder traversal of its nodes’ values. Examples Example 1: 1 \ 2 / 3 Input: root = [1,null,2,3] Output: [1,2,3] ...

Binary Tree DFS Traversal

Binary Tree Traversal - Depth First Search DFS Problem Given a Binary Search Tree, Do the Depth First Search/Traversal . Solution In a Binary Tree, we can do 3 kinds of DFS: Inorder Traversal (Left-Root-Right) - Binary Tree Inorder Traversal Preorder Traversal (Root-Left-Right) - Binary Tree Preorder Traversal Morris Traversal - Inorder Tree Traversal without recursion and without stack but using constant space Postorder Traversal (Left-Right-Root) - Binary Tree Postorder Traversal

Binary Tree Level Order Traversal - Level by Level

Problem 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). NOTE : This problem is very similar to - Create linked lists of all the nodes at each depth for a Binary Tree Examples Example 1: 3 / \ 9 20 / \ 15 7 ...

Binary Tree Traversal - Level Order

Problem Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). Examples Example 1: Given binary tree {3, 9, 20, #, #, 15, 7}, 3 / \ 9 20 / \ 15 7 ...

Binary Tree Traversal - Level Order Bottom up

Problem Given a binary tree, return the bottom-up level order traversal of its nodes’ values. Examples Example 1: 3 / \ 9 20 / \ 15 7 Input: root = [3,9,20,null,null,15,7] Output: [ [15,7],[9,20],[3] ] ...

Recover Binary Search Tree Problem

Recover Binary Search Tree Problem Problem You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? Example Example 1: Input: *1 / *3 \ 2 Output: *3 / *1 \ 2 ...

Construct String from Binary Tree Problem

Problem Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it. Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree. Examples Example 1: 1 / \ 2 3 / 4 ...

Binary Search Tree BST Inorder Iterator

Problem Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST): BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST. boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false. int next() Moves the pointer to the right, then returns the number at the pointer. Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST. ...