Tag Archives: recursion

Inorder Tree Traversal without Recursion: GeeksforGeeks

Problem link: http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

Problem Statement:
It is easy to traverse a binary tree in-order using recursion. Do it without using recursion.
Continue reading

Advertisements

Lowest Common Ancestor in a BST: GeeksforGeeks

Problem link: http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/

Problem Statement:
Given values of two nodes in a Binary Search Tree, write a c program to find the Lowest Common Ancestor (LCA). You may assume that both the values exist in the tree. You can assume that the nodes are present in the tree.
Continue reading

Check for Same BSTs from Arrays: GeeksforGeeks

Problem link: http://www.geeksforgeeks.org/check-for-identical-bsts-without-building-the-trees/

Problem Statement:
Given two arrays which represent a sequence of keys. Imagine we make a Binary Search Tree (BST) from each array. We need to tell whether two BSTs will be identical or not without actually constructing the tree.
For example, the input arrays are {2, 4, 3, 1} and {2, 1, 4, 3} will construct the same tree
Continue reading

Extract Leaves of a Binary Tree in a Doubly Linked List : GeeksforGeeks

Problem link: http://www.geeksforgeeks.org/connect-leaves-doubly-linked-list/

Problem Statement:
Given a Binary Tree, extract all leaves of it in a Doubly Linked List (DLL). Note that the DLL need to be created in-place. Assume that the node structure of DLL and Binary Tree is same, only the meaning of left and right pointers are different. In DLL, left means previous pointer and right means next pointer.
Continue reading

Boundary Traversal of Binary Tree : GeeksforGeeks

Problem link: http://www.geeksforgeeks.org/boundary-traversal-of-binary-tree/

Problem Statement:
Given a binary tree, print boundary nodes of the binary tree Anti-Clockwise starting from the root.
Continue reading

LittleElephantAndBooks: TopCoder Problem 12112

[The problem appeared in TopCoder SRM 592 (Div-2, Level-1)]

Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=12112

Problem Statement:
Little Elephant from the Zoo of Lviv has a bunch of books. You are given a int[] pages. Each element of pages is the number of pages in one of those books. There are no two books with the same number of pages.

You are also given a int number. As a homework from the teacher, Little Elephant must read exactly number of his books during the summer. (Little Elephant has strictly more than number books.)

All other elephants in the school also got the exact same homework. Little Elephant knows that the other elephants are lazy: they will simply pick the shortest number books, so that they have to read the smallest possible total number of pages. Little Elephant wants to be a good student and read a bit more than the other elephants. He wants to pick the subset of books with the second smallest number of pages. In other words, he wants to pick a subset of books with the following properties:

1. There are exactly number books in the chosen subset.
2. The total number of pages of those books is greater than the smallest possible total number of pages.
3. The total number of pages of those books is as small as possible (given the above conditions).

Return the total number of pages Little Elephant will have to read.
Continue reading

Factorial digit sum: Project Euler Problem 20

Problem link: http://projecteuler.net/problem=20

Problem Statement:
n! means n\times(n-1)\times...\times2\times1

For example, 10! = 10 \times 9 \times ... \times 3 \times 2 \times 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

Continue reading