Initial commit.HEADmain

4 files changed, 176 insertions, 0 deletions

diff --git a/top-interview-questions/medium/trees_and_graphs/01_binary_tree_inorder_traversal.cc b/top-interview-questions/medium/trees_and_graphs/01_binary_tree_inorder_traversal.cc
new file mode 100644
index 0000000..6a2762b
--- /dev/null
+++ b/top-interview-questions/medium/trees_and_graphs/01_binary_tree_inorder_traversal.cc
@@ -0,0 +1,27 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+    void inorder(TreeNode* node, vector<int>& vals) {
+        if (node == nullptr) return;
+
+        inorder(node->left, vals);
+        vals.push_back(node->val);
+        inorder(node->right, vals);
+    }
+
+    vector<int> inorderTraversal(TreeNode* root) {
+        vector<int> vals;
+        inorder(root, vals);
+        return vals;
+    }
+};
diff --git a/top-interview-questions/medium/trees_and_graphs/02_binary_tree_zigzag_level_order_traversal.cc b/top-interview-questions/medium/trees_and_graphs/02_binary_tree_zigzag_level_order_traversal.cc
new file mode 100644
index 0000000..2abb093
--- /dev/null
+++ b/top-interview-questions/medium/trees_and_graphs/02_binary_tree_zigzag_level_order_traversal.cc
@@ -0,0 +1,53 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+    void push(vector<const TreeNode*>& level, vector<int>& values, const TreeNode* node) {
+        level.push_back(node);
+        values.push_back(node->val);
+    }
+
+    void zigZag(bool leftRight, const vector<const TreeNode*>& level, vector<vector<int>>& values) {
+        vector<const TreeNode*> next_level;
+        vector<int>             next_values;
+
+        if (leftRight) {
+            for (int i = level.size()-1; i >= 0; --i) {
+                const TreeNode* node = level[i];
+                if (node->left)  push(next_level, next_values, node->left);
+                if (node->right) push(next_level, next_values, node->right);
+            }
+        }
+        else {
+            for (int i = level.size()-1; i >= 0; --i) {
+                const TreeNode* node = level[i];
+                if (node->right) push(next_level, next_values, node->right);
+                if (node->left)  push(next_level, next_values, node->left);
+            }
+        }
+
+        if (!next_level.empty()) {
+            values.push_back(next_values);
+            zigZag(!leftRight, next_level, values);
+        }
+    }
+
+    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
+        if (root == nullptr) return {};
+
+        vector<const TreeNode*> level  = {root};
+        vector<vector<int>>     values = {{root->val}};
+
+        zigZag(false, level, values);
+        return values;
+    }
+};
diff --git a/top-interview-questions/medium/trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder_traversal.cc b/top-interview-questions/medium/trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder_traversal.cc
new file mode 100644
index 0000000..95e3655
--- /dev/null
+++ b/top-interview-questions/medium/trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder_traversal.cc
@@ -0,0 +1,49 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+    TreeNode* build(const vector<int>& preorder, const vector<int>& inorder,
+                    int& preIdx, int leftIdx, int rightIdx) {
+        // Base case.
+        if (leftIdx > rightIdx) {
+            return nullptr;
+        }
+
+        // Root value.
+        const int root = preorder[preIdx++];
+
+        // Base case.
+        if (leftIdx == rightIdx) {
+            return new TreeNode{root, nullptr, nullptr};
+        }
+        // Recursive case.
+        else {
+            // Find the root in the inorder array.
+            int inorderRootIdx = -1;
+            for (int i = 0; i < inorder.size(); ++i) {
+                if (inorder[i] == root) {
+                    inorderRootIdx = i;
+                    break;
+                }
+            }
+            // Build recursively.
+            TreeNode* left  = build(preorder, inorder, preIdx, leftIdx, inorderRootIdx-1);
+            TreeNode* right = build(preorder, inorder, preIdx, inorderRootIdx+1, rightIdx);
+            return new TreeNode{root, left, right};
+        }
+    }
+
+    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
+        int preIdx = 0;
+        return build(preorder, inorder, preIdx, 0, preorder.size()-1);
+    }
+};
diff --git a/top-interview-questions/medium/trees_and_graphs/04_populating_next_right_pointers_in_each_node.cc b/top-interview-questions/medium/trees_and_graphs/04_populating_next_right_pointers_in_each_node.cc
new file mode 100644
index 0000000..17a5874
--- /dev/null
+++ b/top-interview-questions/medium/trees_and_graphs/04_populating_next_right_pointers_in_each_node.cc
@@ -0,0 +1,47 @@
+/*
+// Definition for a Node.
+class Node {
+public:
+    int val;
+    Node* left;
+    Node* right;
+    Node* next;
+
+    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
+
+    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
+
+    Node(int _val, Node* _left, Node* _right, Node* _next)
+        : val(_val), left(_left), right(_right), next(_next) {}
+};
+*/
+
+class Solution {
+public:
+    // The obvious solution is to do a BFS and connect the nodes in each level.
+    // However, the problem asks us to use "constant space" (depth of tree).
+
+    void connectLeftRight(Node* leftTree, Node* rightTree) {
+        while (leftTree && rightTree) {
+            leftTree->next = rightTree;
+
+            leftTree  = leftTree->right;
+            rightTree = rightTree->left;
+        }
+    }
+
+    Node* connect(Node* root) {
+        if (root == nullptr) {
+            return root;
+        }
+
+        connect(root->left);
+        connect(root->right);
+
+        if (root->left) { // Non-leaf node.
+            connectLeftRight(root->left, root->right);
+        }
+
+        return root;
+    }
+};