Binary_Tree Class Reference

#include <binary_tree.h>

Public Member Functions
TreeNode *	newNode (int val)
	Allocate the dynamic memory to a new node and assign a value. More...
void	printinOrder (TreeNode *root)
	Print tree nodes in In-order traversal. More...
TreeNode *	insertNode (int arr[], TreeNode *root, int idx, int size)
	Construct binary tree node from given array in level order. More...
bool	findtwosumTarget (TreeNode *root, int target)
	Two Sum IV - Input is a BST - Easy. More...
void	storinginOrder (TreeNode *root, vector< int > &num)
	In-order storing the binary tree value into vector. More...

Member Function Documentation

findtwosumTarget()

bool Binary_Tree::findtwosumTarget	(	TreeNode *	root,
		int	target
	)

Two Sum IV - Input is a BST - Easy.

Parameters

Binary	search tree
Target	number

Returns

True if there exists two elements such that their sum is equal to the given target

Ideal:

1. Using recursive traversal to transfer tree node into vector array
2. Determine whether there exists the sum of two value is same as target number

{
    int i, j;
    bool result = false;
    vector<int> nums;

    // Transfer tree node into vector array
    storinginOrder(root, nums);

    for (i = 0, j = (int) nums.size() - 1; i < j;) {
        if (nums[i] + nums[j] == target)
            result = true;

        nums[i] + nums[j] < target ? ++ i: -- j;
    }
    return result;
}

Referenced by leetcode_practice().

insertNode()

TreeNode * Binary_Tree::insertNode	(	int	arr[],
		TreeNode *	root,
		int	idx,
		int	size
	)

Construct binary tree node from given array in level order.

Parameters

Given	array
Parent	binary tree node
Given	level
Total	size of the given array

Returns

Constructed binary tree node

Ideal:

1. Insert the left node firstly (0 -> 1 -> 3)
2. Second, insert the right node firstly (4 -> 2)
3. Insert the rest of node (5)

Input: { 5, 3, 6, 2, 4, 7} 5 / \ 3 6 / \ / 2 4 7

{
    // protect to avoid over the range of array
    if (idx < size) {

        // New node
        TreeNode* root_tmp = newNode(arr[idx]);
        root = root_tmp;

        // insert left side
        root->left = insertNode(arr, root->left, 2*idx + 1, size);

        // insert right side
        root->right = insertNode(arr, root->right, 2*idx + 2, size);
    }
    return root;
}

Referenced by leetcode_practice().

newNode()

TreeNode * Binary_Tree::newNode

(

int

val

)

Allocate the dynamic memory to a new node and assign a value.

Parameters

Given

value

Returns

New node

{
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = val;
    root->left = root->right = NULL;

    return root;
}

printinOrder()

void Binary_Tree::printinOrder

(

TreeNode *

root

)

Print tree nodes in In-order traversal.

Parameters

Parent

binary tree node

Returns

None

{
    if (root != NULL)
    {
        printinOrder(root->left);
        cout << "" << root->val << endl;
        printinOrder(root->right);
    }
}

storinginOrder()

void Binary_Tree::storinginOrder	(	TreeNode *	root,
		vector< int > &	num
	)

In-order storing the binary tree value into vector.

Parameters

Parent	binary tree node
Vector	dynamic array

Returns

None 0

{
    // Protect infinite recursive loop
    if (!root)
        return;

    storinginOrder(root->left, num);
    num.push_back(root->val);
    storinginOrder(root->right, num);
}

---

The documentation for this class was generated from the following files:

• array/binary_tree.h
• array/binary_tree.cpp