Category Archives: Tree

Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = “great”: great / \ gr eat / \ / \ g r e at / \ … Continue reading

Posted in Recursive, Tree | Leave a comment

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively? C++: 01 /** 02  * Definition for binary tree 03  * … Continue reading

Posted in Stack and Queue, Tree | Leave a comment

Unique Binary Search Trees II

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n. For example, Given n = 3, your program should return all 5 unique BST’s shown below. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 … Continue reading

Posted in Dynamic programming, Recursive, Tree | Leave a comment

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n? For example, Given n = 3, there are a total of 5 unique BST’s. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 … Continue reading

Posted in Dynamic programming, Tree | Leave a comment

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a … Continue reading

Posted in Recursive, Tree | Leave a comment

Recover Binary Search Tree

Two elements of a binary search tree (BST) are 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? C++: 01 /** 02  * … Continue reading

Posted in Recursive, Tree | Leave a comment

Same Tree

Given two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value. C++: 01 /** 02  * Definition for binary … Continue reading

Posted in Recursive, Tree | Leave a comment