# National Cheng Kung University - Practical Overview of Technology Industrial
## 1. Binary Tree
### **Inorder Tree Traversal – Iterative and Recursive**
Traversing a tree involves iterating over all nodes in some manner. As the tree is not a linear data structure, there can be more than one possible next node from a given node, so some nodes must be deferred, i.e., stored in some way for later visiting. The traversal can be done iteratively where the deferred nodes are stored in the stack, or it can be done by recursion, where the deferred nodes are stored implicitly in the call stacl
For traversing a (non-empty) binary tree in an inorder fashion, we must do these three things for every node n starting from the tree’s root:
> (L) Recursively traverse its left subtree. When this step is finished, we are back at n again.
(N) Process n itself.
(R) Recursively traverse its right subtree. When this step is finished, we are back at n again.
In normal inorder traversal, we visit the left subtree before the right subtree. If we visit the right subtree before visiting the left subtree, it is referred to as reverse inorder traversal.
1. ### Recursive Implementation
As we can see, before processing any node, the left subtree is processed first, followed by the node, and the right subtree is processed at last. These operations can be defined recursively for each node. The recursive implementation is referred to as a Depth–first search (DFS), as the search tree is deepened as much as possible on each child before going to the next sibling.
```
#include <iostream>
using namespace std;
// Data structure to store a binary tree node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
// Recursive function to perform inorder traversal on the tree
void inorder(Node* root)
{
// return if the current node is empty
if (root == nullptr) {
return;
}
// Traverse the left subtree
inorder(root->left);
// Display the data part of the root (or current node)
cout << root->data << " ";
// Traverse the right subtree
inorder(root->right);
}
int main()
{
/* Construct the following tree
1
/ \
/ \
2 3
/ / \
/ / \
4 5 6
/ \
/ \
7 8
*/
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(6);
root->right->left->left = new Node(7);
root->right->left->right = new Node(8);
inorder(root);
return 0;
}
```
## 2.Happy Number
A Happy Number n is defined by the following process. Starting with n, replace it with the sum of the squares of its digits, and repeat the process until n equals 1, or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are Happy Numbers, while those that do not end in 1 are unhappy numbers. First few happy numbers are 1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100
> Explanation Each Iteration
> Input: n = 19
Output: True
19 is Happy Number,
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
As we reached to 1, 19 is a Happy Number.
Input: n = 20
Output: False
> Problem Solution
> we can repeated do sum of squares of digits. While doing so, we keep track of visited numbers using a hash. If we reach 1, we return true. Else if we reach a visited a number, we return false.
```
#include <iostream>
using namespace std;
// Function for return sum of squares of digits
int sumDigitSquare(int n)
{
int sq = 0;
while (n) {
int digit = n % 10;
sq += digit * digit;
n = n / 10;
}
return sq;
}
//condtion statment true if n is Happy number
bool isHappy(int n)
{
// A set to store numbers during repeated square sum process
set<int> s;
s.insert(n);
// Keep replacing n with sum of squares
while (1) {
// Number is Happy if we reach 1
if (n == 1)
return true;
// Replace n with sum of squares of digits
n = sumDigitSquare(n);
// If n is already visited, a cycle is formed, means not Happy
if (s.find(n) != s.end())
return false;
// Mark n as visited
s.insert(n);
}
return false;
}
int main()
{
int n = 19;
if (isHappy(n))
cout << "True" << endl;
else
cout << "False" << endl;
return 0;
}
```
## 3.Stair Climbing
There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top.
Consider the example shown in the diagram. The value of n is 3. There are 3 ways to reach the top
> Explanation
> Input: n = 2
Output: 2
There are two ways: (1, 1) and (2)
In this Case I use method of the technique of recursion to solve this problem.
Approach: We can easily find the recursive nature in the above problem. The person can reach nth stair from either (n-1)th stair or from (n-2)th stair. Hence, for each stair n, we try to find out the number of ways to reach n-1th stair and n-2th stair and add them to give the answer for the nth stair. Therefore the expression for such an approach comes out to be :
> ways(n) = ways(n-1) + ways(n-2)
The above expression is actually the expression for Fibonacci numbers, but there is one thing to notice, the value of ways(n) is equal to fibonacci(n+1).
> ways(1) = fib(2) = 1
ways(2) = fib(3) = 2
ways(3) = fib(4) = 3
```
#include <iostream>
using namespace std;
// recursive function to find N'th fibonacci number
int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
// function number of ways to reach s'th stair
int countWays(int s)
{
return fib(s + 1);
}
int main()
{
int s = 4;
cout << "Number of ways = " << countWays(s);
return 0;
}
```
Refererence :
1. [https://en.wikipedia.org/wiki/Tree_traversal](https://)
2. [https://en.wikipedia.org/wiki/Happy_number](https://)
3. [https://en.wikipedia.org/wiki/Stair_climbing](https://)
Sign in with Wallet
Connect another wallet