Code for following problems:
1. Given a binary tree, count the number of nodes in the tree.
2. Given a binary tree, compute its "maxDepth" -- the number of nodes along the longest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0.
3. Given a non-empty binary search tree (an ordered binary tree), return the minimum data value found in that tree. Note that it is not necessary to search the entire tree. A maxValue() function is structurally very similar to this function.
4. Given a binary search tree (aka an "ordered binary tree"), iterate over the nodes to print them out in increasing order.
5. Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found.
6. Given a binary tree, print out all of its root-to-leaf paths, one per line.
7. Change a tree so that the roles of the left and right pointers are swapped at every node.
8. Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way.
9. Suppose you are building an N node binary search tree with the values 1..N. How many structurally different
binary search trees are there that store those values? Write a recursive function that, given the number of distinct values, computes the number of structurally unique binary search trees that store those values. For example, countTrees(4) should return 14, since there are 14 structurally unique binary search trees that store 1, 2, 3, and 4. The base case is easy, and the recursion is short but dense. Your code should not construct any actual trees; it's just a
counting problem.
10. Write an isBST() function that returns true if a tree is a binary search tree
and false otherwise.
Code:
1. Given a binary tree, count the number of nodes in the tree.
2. Given a binary tree, compute its "maxDepth" -- the number of nodes along the longest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0.
3. Given a non-empty binary search tree (an ordered binary tree), return the minimum data value found in that tree. Note that it is not necessary to search the entire tree. A maxValue() function is structurally very similar to this function.
4. Given a binary search tree (aka an "ordered binary tree"), iterate over the nodes to print them out in increasing order.
5. Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found.
6. Given a binary tree, print out all of its root-to-leaf paths, one per line.
7. Change a tree so that the roles of the left and right pointers are swapped at every node.
8. Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way.
9. Suppose you are building an N node binary search tree with the values 1..N. How many structurally different
binary search trees are there that store those values? Write a recursive function that, given the number of distinct values, computes the number of structurally unique binary search trees that store those values. For example, countTrees(4) should return 14, since there are 14 structurally unique binary search trees that store 1, 2, 3, and 4. The base case is easy, and the recursion is short but dense. Your code should not construct any actual trees; it's just a
counting problem.
10. Write an isBST() function that returns true if a tree is a binary search tree
and false otherwise.
Code:
No comments:
Post a Comment